题意：在一个二维坐标系中，每次有两个操作：
①向一个点加入一种颜色。
②询问矩形区域[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);
}
}
}