题意：在一个二维坐标系中，每次有两个操作：
①向一个点加入一种颜色。
②询问矩形区域[1,y1],[x,y2]范围内的不同颜色的数量。
题解：这道题一共四个维度，我们可以这样分配：x轴排序，时间用cdq分治，y坐标用线段树，颜色用位压缩（64位表示）。
（比赛的时候用kdtree过的= =，后来发现cdq分治还比kdtree快= =）
AC代码：
#include<stdio.h> #include<algorithm> #include<string.h> #define N 150005 using namespace std; typedef long long ll; struct node { int op; ll q[3]; int t; }Q[N],SQ[N]; ll b[N*2]; bool cmp(node a,node b) { if(a.q[0]==b.q[0])return a.op<b.op; return a.q[0]<b.q[0]; } ll ans[N],tree[N*4]; int top; void update(int x,int L,int R,ll w,int root,int flag) { if(L==R) { if(!flag)tree[root]|=w; else tree[root]=0; return ; } int mid=L+R>>1; if(x<=mid)update(x,L,mid,w,root<<1,flag); else update(x,mid+1,R,w,root<<1|1,flag); if(!flag)tree[root]=tree[root<<1]|tree[root<<1|1]; else tree[root]=0; } ll query(int l,int r,int L,int R,int root) { if(l<=L&&R<=r) return tree[root]; int mid=L+R>>1; if(r<=mid)return query(l,r,L,mid,root<<1); else if(l>mid)return query(l,r,mid+1,R,root<<1|1); else return query(l,mid,L,mid,root<<1)|query(mid+1,r,mid+1,R,root<<1|1); } void solve(int L,int R) { if(L>=R)return ; int mid=L+R>>1; for(int i=L;i<=R;i++) { if(Q[i].t<=mid&&Q[i].op==1)update(Q[i].q[1],1,top,(1ll<<Q[i].q[2]),1,0); else if(Q[i].t>mid&&Q[i].op==2)ans[Q[i].t]|=query(Q[i].q[1],Q[i].q[2],1,top,1); } for(int i=L;i<=R;i++) if(Q[i].t<=mid&&Q[i].op==1)update(Q[i].q[1],1,top,(1ll<<Q[i].q[2]),1,1); int l=L; for(int i=L;i<=R;i++) if(Q[i].t<=mid) SQ[l++]=Q[i]; int r=l; for(int i=L;i<=R;i++) if(Q[i].t>mid) SQ[r++]=Q[i]; for(int i=L;i<=R;i++) Q[i]=SQ[i]; solve(L,l-1); solve(l,R); } int main() { int o; scanf("%d",&o); while(1) { memset(ans,0,sizeof(ans)); memset(tree,0,sizeof(tree)); if(o==3)break; int tot=0;top=0; while(1) { scanf("%d",&Q[tot].op),o=Q[tot].op; if(o==0||o==3)break; scanf("%lld%lld%lld",&Q[tot].q[0],&Q[tot].q[1],&Q[tot].q[2]); Q[tot].t=tot;b[top++]=Q[tot].q[1];b[top++]=Q[tot].q[2]; tot++; } sort(b,b+top); top=unique(b,b+top)-b; for(int i=0;i<tot;i++) { int pos=lower_bound(b,b+top,Q[i].q[1])-b; Q[i].q[1]=pos+1; if(Q[i].op==2) { pos=lower_bound(b,b+top,Q[i].q[2])-b; Q[i].q[2]=pos+1; } } sort(Q,Q+tot,cmp); solve(0,tot-1); for(int i=0;i<tot;i++) { if(Q[i].op==1)continue; int ansha=0; for(ll j=0;j<=50;j++) if(ans[i]&(1ll<<j)) ansha++; printf("%d\n",ansha); } } }
