Description
有 N 个彩色糖果在平面上。小奇想在平面上取一条水平的线段,并拾起它上方或下方的所有糖果。求出最多能够拾
起多少糖果,使得获得的糖果并不包含所有的颜色。
Input
包含多组测试数据,第一行输入一个正整数 T 表示测试数据组数。
接下来 T 组测试数据,对于每组测试数据,第一行输入两个正整数 N、K,分别表示点数和颜色数。
接下来 N 行,每行描述一个点,前两个数 x, y (|x|, |y| ≤ 2^30 - 1) 描述点的位置,最后一个数 z (1 ≤ z ≤
k) 描述点的颜色。
对于 100% 的数据,N ≤ 100000,K ≤ 100000,T ≤ 3
Output
对于每组数据在一行内输出一个非负整数 ans,表示答案
枚举哪种颜色不选
存在一个最优解，使所选区域三边都 紧靠着不可选的点 或 可延伸到无限远
找出符合这个条件的O(n)个区域，用扫描线求出点数
#include<cstdio> #include<cstring> #include<algorithm> #define G *++ptr const int N=100007; char buf[N*100],*ptr=buf-1; int _(){ int x=0,c=G,f=1; while(c<48)c=='-'&&(f=-1),c=G; while(c>47)x=x*10+c-48,c=G; return x*f; } int n,k,ans; struct pos{ int x,y,c; bool operator<(const pos&w)const{return x<w.x;} }ps[N]; bool cmp(const pos&a,const pos&b){return a.y<b.y;} struct pt{ int x,y; }mem[N],*mp,*ls[N],*rs[N]; struct Q{ int y,l,r; }qs1[N],qs2[N]; bool cmp1(const Q&a,const Q&b){return a.y>b.y;} bool cmp2(const Q&a,const Q&b){return a.y<b.y;} int xs[N],ys[N],cs[N],bit[N],ts[N],qp1,qp2; void inc(int w){ for(;w<=n;w+=w&-w)++bit[w]; } int sum(int w){ int s=0; for(;w;w-=w&-w)s+=bit[w]; return s; } void mins(int&a,int b){if(a>b)a=b;} void maxs(int&a,int b){if(a<b)a=b;} pt p1[N],p2[N]; int pp1,pp2,ss[N],sp,l1[N],r1[N],l2[N],r2[N]; void cal(pt*l,pt*r){ if(l==r){ ans=n; return; } pp1=pp2=0; maxs(ans,ts[l->x-1]); maxs(ans,ts[n]-ts[r[-1].x]); for(pt*m=l;l<r;l=m){ int ymx=l->y,ymn=l->y; while(m<r&&m->x==l->x)maxs(ymx,m->y),mins(ymn,m->y),++m; if(m<r)maxs(ans,ts[m->x-1]-ts[l->x]); p1[++pp1]=(pt){l->x,ymx}; p2[++pp2]=(pt){l->x,ymn}; } sp=0; for(int i=1;i<=pp1;++i){ while(sp&&p1[ss[sp]].y<p1[i].y)r1[ss[sp--]]=p1[i].x-1; ss[++sp]=i; } while(sp)r1[ss[sp--]]=n; for(int i=pp1;i;--i){ while(sp&&p1[ss[sp]].y<p1[i].y)l1[ss[sp--]]=p1[i].x+1; ss[++sp]=i; } while(sp)l1[ss[sp--]]=1; for(int i=1;i<=pp1;++i)qs1[qp1++]=(Q){p1[i].y,l1[i],r1[i]}; for(int i=1;i<=pp2;++i){ while(sp&&p2[ss[sp]].y>p2[i].y)r2[ss[sp--]]=p2[i].x-1; ss[++sp]=i; } while(sp)r2[ss[sp--]]=n; for(int i=pp2;i;--i){ while(sp&&p2[ss[sp]].y>p2[i].y)l2[ss[sp--]]=p2[i].x+1; ss[++sp]=i; } while(sp)l2[ss[sp--]]=1; for(int i=1;i<=pp2;++i)qs2[qp2++]=(Q){p2[i].y,l2[i],r2[i]}; } int main(){ fread(buf,1,sizeof(buf),stdin)[buf]=0; for(int T=_();T;--T){ n=_();k=_(); ans=0;qp1=qp2=0; memset(cs,0,sizeof(int)*(k+2)); memset(ts,0,sizeof(int)*(n+2)); mp=mem; for(int i=1;i<=n;++i){ ps[i].x=xs[i]=_(); ps[i].y=ys[i]=_(); ++cs[ps[i].c=_()]; } std::sort(xs+1,xs+n+1); std::sort(ys+1,ys+n+1); for(int i=1;i<=n;++i){ ps[i].x=std::lower_bound(xs+1,xs+n+1,ps[i].x)-xs; ps[i].y=std::lower_bound(ys+1,ys+n+1,ps[i].y)-ys; ++ts[ps[i].x]; } std::sort(ps+1,ps+n+1); for(int i=1;i<=n;++i)ts[i]+=ts[i-1]; for(int i=1;i<=k;++i)ls[i]=rs[i]=mp,mp+=cs[i]; for(int i=1;i<=n;++i)*rs[ps[i].c]++=(pt){ps[i].x,ps[i].y}; for(int i=1;i<=k;++i)cal(ls[i],rs[i]); std::sort(ps+1,ps+n+1,cmp); std::sort(qs1,qs1+qp1,cmp1); std::sort(qs2,qs2+qp2,cmp2); memset(bit,0,sizeof(int)*(n+2)); for(int i=0,j=n;i<qp1;++i){ while(j&&ps[j].y>qs1[i].y)inc(ps[j--].x); int z; maxs(ans,z=sum(qs1[i].r)-sum(qs1[i].l-1)); } memset(bit,0,sizeof(int)*(n+2)); for(int i=0,j=1;i<qp2;++i){ while(j<=n&&ps[j].y<qs2[i].y)inc(ps[j++].x); maxs(ans,sum(qs2[i].r)-sum(qs2[i].l-1)); } printf("%d ",ans); } return 0; }