题目大意：给定平面上n个点，一共有k种颜色，要求选定一条线段，，并选取线段正上方或正下方的所有点，要求不能出现所有颜色的点，求最多选择多少点
正解是双向链表+树状数组？
让我们来点优雅的做法
由于不能出现所有颜色的点 因此一定有至少一种颜色不出现 我们可以枚举这个不出现的颜色
现在我们搞出所有极大子矩形
这个分治就好了。。。
假设我们现在求的是一条线段下方的点 那么我们考虑一条直线从下往上走 遇到禁止的点就分成两段 继续
那么我们利用分治来模拟这个过程
定义Solve(l,r)为处理横坐标在[l,r]区间内的点
那么我们寻找横坐标在[l,r]区间内的y值最小的点p
如果不存在这个点 就直接用左上角为(l,INF)，右下角为(r,-INF)的矩形来更新答案
如果存在这个点 就用左上角为(l,p.y)，右下角为(r,-INF)的矩形来更新答案，然后递归处理[l,p.x-1]和[p.x+1,y]
那么我们怎么统计某个矩形中有多少点呢？
主席树搞一搞就可以辣！！
一开始脑残写了个树套树T到死。。。
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define M 100100using namespace std;namespace Functional_Segtree{struct Segtree{Segtree *ls,*rs;int val;void* operator new (size_t,Segtree *_,Segtree *__,int ___);}*tree[M],mempool[2000000],*C=mempool,*root;void* Segtree :: operator new (size_t,Segtree *_,Segtree *__,int ___){C->ls=_;C->rs=__;C->val=___;return C++;}Segtree* Insert(Segtree *p,int x,int y,int pos){int mid=x+y>>1;if(x==y)return new (0x0,0x0,p->val+1)Segtree;if(pos<=mid)return new (Insert(p->ls,x,mid,pos),p->rs,p->val+1)Segtree;elsereturn new (p->ls,Insert(p->rs,mid+1,y,pos),p->val+1)Segtree;}int Query(Segtree *p1,Segtree *p2,int x,int y,int l,int r){int mid=x+y>>1;if(x==l&&y==r)return p2->val – p1->val;if(r<=mid)return Query(p1->ls,p2->ls,x,mid,l,r);if(l>mid)return Query(p1->rs,p2->rs,mid+1,y,l,r);return Query(p1->ls,p2->ls,x,mid,l,mid) + Query(p1->rs,p2->rs,mid+1,y,mid+1,r);}void Initialize(){C=mempool;tree[0]=new (0x0,0x0,0)Segtree;tree[0]->ls=tree[0]->rs=tree[0];}}struct Point{int x,y;bool operator < (const Point &p) const{return x < p.x;}}points[M],_points[M];bool Compare1(int x,int y){return points[x].y < points[y].y;}bool Compare2(int x,int y){if(x==0) return true;if(y==0) return false;return points[x].y > points[y].y;}namespace Segment_Tree{struct Segtree{Segtree *ls,*rs;int max_pos;void* operator new (size_t);}mempool[M<<1],*C=mempool,*root;void Initialize(){C=mempool;root=0x0;}void* Segtree :: operator new (size_t){C->ls=C->rs=0x0;C->max_pos=0;return C++;}void Insert(Segtree *&p,int x,int y,int pos,bool(&Compare)(int,int)){int mid=x+y>>1;if(!p) p=new Segtree;if(x==y){p->max_pos=max(p->max_pos,pos,Compare);return ;}if(points[pos].x<=mid)Insert(p->ls,x,mid,pos,Compare);elseInsert(p->rs,mid+1,y,pos,Compare);p->max_pos=max( (p->ls?p->ls->max_pos:0) , (p->rs?p->rs->max_pos:0) , Compare );}int Query(Segtree *p,int x,int y,int l,int r,bool(&Compare)(int,int)){int mid=x+y>>1;if(!p) return 0;if(x==l&&y==r)return p->max_pos;if(r<=mid)return Query(p->ls,x,mid,l,r,Compare);if(l>mid)return Query(p->rs,mid+1,y,l,r,Compare);return max( Query(p->ls,x,mid,l,mid,Compare) , Query(p->rs,mid+1,y,mid+1,r,Compare) , Compare );}}int n,k,ans;int a[M],c[M];pair<int,int*> b[M];bool Compare(int x,int y){return a[x] < a[y];}void Divide_And_Conquer1(int l,int r){if(l>r) return ;int mid=Segment_Tree::Query(Segment_Tree::root,1,n,l,r,Compare1);if(!mid){ans=max(ans,Functional_Segtree::Query(Functional_Segtree::tree[l-1],Functional_Segtree::tree[r],1,n,1,n));return ;}if(points[mid].y<n)ans=max(ans,Functional_Segtree::Query(Functional_Segtree::tree[l-1],Functional_Segtree::tree[r],1,n,points[mid].y+1,n));Divide_And_Conquer1(l,points[mid].x-1);Divide_And_Conquer1(points[mid].x+1,r);}void Divide_And_Conquer2(int l,int r){if(l>r) return ;int mid=Segment_Tree::Query(Segment_Tree::root,1,n,l,r,Compare2);if(!mid){ans=max(ans,Functional_Segtree::Query(Functional_Segtree::tree[l-1],Functional_Segtree::tree[r],1,n,1,n));return ;}if(points[mid].y>1)ans=max(ans,Functional_Segtree::Query(Functional_Segtree::tree[l-1],Functional_Segtree::tree[r],1,n,1,points[mid].y-1));Divide_And_Conquer2(l,points[mid].x-1);Divide_And_Conquer2(points[mid].x+1,r);}int main(){freopen("jabber.in","r",stdin);freopen("jabber.out","w",stdout);int T,i,j;srand(19980402);for(cin>>T;T;T–){Functional_Segtree::Initialize();ans=0;cin>>n>>k;for(i=1;i<=n;i++){scanf("%d%d%d",&points[i].x,&points[i].y,&a[i]);c[i]=i;}sort(c+1,c+n+1,Compare);for(i=1;i<=n;i++)b[i]=make_pair(points[i].x,&points[i].x);sort(b+1,b+n+1);int tot=0;for(i=1;i<=n;i++){if(i==1||b[i].first!=b[i-1].first)++tot;*b[i].second=tot;}for(i=1;i<=n;i++)b[i]=make_pair(points[i].y,&points[i].y);sort(b+1,b+n+1);tot=0;for(i=1;i<=n;i++){if(i==1||b[i].first!=b[i-1].first)++tot;*b[i].second=tot;}memcpy(_points,points,sizeof points);sort(_points+1,_points+n+1);for(j=1,i=1;i<=n;i++){Functional_Segtree::tree[i]=Functional_Segtree::tree[i-1];for(;_points[j].x==i;j++)Functional_Segtree::tree[i]=Functional_Segtree::Insert(Functional_Segtree::tree[i],1,n,_points[j].y);}//上半部分for(j=1,i=1;i<=k;i++){Segment_Tree::Initialize();for(;j<=n&&a[c[j]]==i;j++)Segment_Tree::Insert(Segment_Tree::root,1,n,c[j],Compare1);Divide_And_Conquer1(1,n);}//下半部分for(j=1,i=1;i<=k;i++){Segment_Tree::Initialize();for(;j<=n&&a[c[j]]==i;j++)Segment_Tree::Insert(Segment_Tree::root,1,n,c[j],Compare2);Divide_And_Conquer2(1,n);}cout<<ans<<endl;}return 0;}
人性最可怜的就是：我们总是梦想着天边的一座奇妙的玫瑰园，
