【NOIP2018提高组模拟9.20】 有所失

本文主要是介绍【NOIP2018提高组模拟9.20】 有所失，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

Input

Output

若干行，对每个1操作，输出到这个点最多经过多少点。

Sample Input

样例输入1
3 5
1 0 0 1
0 0
1 0
0 1
5
1 3
2 1 1
1 4
2 2 2
1 5

样例输入2
3 5
2 1 1 2
0 0
1 0
0 1
5
1 3
2 1 1
1 4
2 2 2
1 5

Sample Output

样例输出1

2
3
4

样例输出2

1
2
3

Data Constraint

$n,m<=100000，k<=20$

Solution

首先我们想办法把坐标系弄一下变成直角坐标系。
对于每个点，求出它到给定两个边界的三角形的有向面积，以面积的大小为新的下标，并离散化。
可以发现，这样之后，每个点依然满足没有重合而且边界就变成了一个直角的边界。
因为k比较小，考虑从k入手。
把最右边和最上面的k个点分别放到两个队列里，其他不在队列里的点的答案是不会变的，将这些点放到数据结构里。
提前预处理好每个点的答案，然后考虑加入。
预处理相当于二维偏序问题，扫描线加树状数组。
加入时，取出最右和最上的共2k个点，直接暴力转移得到这2k个点的新答案，随后求出新的最右和最上的k个点，多余出的那个点加入数据结构。
发现数据结构的功能只是前缀取max和单点修改，用树状数组即可。
这样有个800的常数，不过不会超时。
时间复杂度$O(mlogn)$

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define N 201000
#define ll long long
using namespace std;
int n,K,m,ni;
struct P{ll x,y,z;
}a[N],X,Y,c[N];
int q[N][2],f[N],t[2][N],b[2][N],bz[N];
ll abx(ll x){return x>0?x:-x;}
ll cross(P a,P b){return a.x*b.y-a.y*b.x;}
bool cnt1(P a,P b){return cross(a,Y)<cross(b,Y);}
bool cnt2(P a,P b){return cross(X,a)<cross(X,b);}
bool cmt1(P a,P b){return (a.x<b.x)||(a.x==b.x&&a.y<b.y);}
bool cmt2(P a,P b){return (a.y<b.y)||(a.y==b.y&&a.x<b.x);}
bool cid(P a,P b){return a.z<b.z;}
int lowbit(int x){return x&(-x);}
void lsh()
{fo(i,1,ni) c[i]=a[i];sort(c+1,c+ni+1,cnt1);int k=0;fo(i,1,ni){if(i==1||cnt1(c[i-1],c[i])) k++;a[c[i].z].x=k;}sort(c+1,c+ni+1,cnt2);k=0;fo(i,1,ni){if(i==1||cnt2(c[i-1],c[i])) k++;a[c[i].z].y=k;}
}
void ins(int q,int x,int z)
{for(;x<=ni;x+=lowbit(x)) t[q][x]=max(t[q][x],z);
}
int get(int q,int x)
{int ans=0;for(;x;x-=lowbit(x)) ans=max(ans,t[q][x]);return ans;
}
void pre()
{sort(a+1,a+ni+1,cmt1);fo(i,1,ni)if(a[i].z<=n){int j=a[i].z;f[j]=get(0,a[i].y)+1;ins(0,a[i].y,f[j]);}memset(t[0],0,sizeof(t[0]));int jy=0;fd(i,ni,1)if(a[i].z<=n){if(jy>=K) ins(0,a[i].y,f[a[i].z]);else b[0][++jy]=a[i].z;}sort(a+1,a+ni+1,cmt2);jy=0;fd(i,ni,1)if(a[i].z<=n){if(jy>=K) ins(1,a[i].x,f[a[i].z]);else b[1][++jy]=a[i].z;}sort(a+1,a+ni+1,cid);
}
int main()
{freopen("travel.in","r",stdin);freopen("travel.out","w",stdout);scanf("%d%d",&n,&K);ni=n;scanf("%lld%lld%lld%lld",&X.x,&X.y,&Y.x,&Y.y);fo(i,1,n) scanf("%lld%lld",&a[i].x,&a[i].y),a[i].z=i;scanf("%d",&m);fo(i,1,m){scanf("%d",&q[i][0]);if(q[i][0]==2||q[i][0]==3){q[i][1]=++ni;scanf("%lld%lld",&a[ni].x,&a[ni].y),a[ni].z=ni;}else scanf("%d",&q[i][1]);}lsh();pre();int numb=0;memset(c,0,sizeof(c));fo(i,1,m){int x=q[i][1];if(q[i][0]==1){numb++;printf("%d\n",f[x]);}else{if(q[i][0]==2) f[x]=get(1,a[x].x)+1;else f[x]=get(0,a[x].y)+1;fo(j,1,K) c[j+j-1]=a[b[0][j]],c[j+j]=a[b[1][j]];c[K+K+1]=a[x];sort(c+1,c+K+K+2,cmt1);fo(j,1,K+K+1) if(c[j].z!=0) fo(k,j+1,K+K+1) if(c[j].z!=c[k].z&&c[k].z!=0&&c[j].x<=c[k].x&&c[j].y<=c[k].y) f[c[k].z]=max(f[c[k].z],f[c[j].z]+1);int jy=0;fd(j,K+K+1,1)if(!bz[c[j].z]){bz[c[j].z]=1;if(jy>=K) ins(0,c[j].y,f[c[j].z]);else b[0][++jy]=c[j].z;}fo(j,1,K+K+1) bz[c[j].z]=0;jy=0;sort(c+1,c+K+K+2,cmt2);fd(j,K+K+1,1)if(!bz[c[j].z]){bz[c[j].z]=1;if(jy>=K) ins(1,c[j].x,f[c[j].z]);else b[1][++jy]=c[j].z;}fo(j,1,K+K+1) bz[c[j].z]=0;}}
}

这篇关于【NOIP2018提高组模拟9.20】 有所失的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---