Do you like painting? Little D doesn’t like painting, especially messy color paintings. Now Little B is painting. To prevent him from drawing messy painting, Little D asks you to write a program to maintain following operations. The specific format of these operations is as follows.
00 : clear all the points.
11 xx yy cc : add a point which color is cc at point (x,y)(x,y).
22 xx y1y1 y2y2 : count how many different colors in the square (1,y1)(1,y1) and (x,y2)(x,y2). That is to say, if there is a point (a,b)(a,b) colored cc, that 1≤a≤x1≤a≤x and y1≤b≤y2y1≤b≤y2, then the color cc should be counted.
33 : exit. Input The input contains many lines.
Each line contains a operation. It may be ‘0’, ‘1 x y c’ ( 1≤x,y≤106,0≤c≤501≤x,y≤106,0≤c≤50 ), ‘2 x y1 y2’ (1≤x,y1,y2≤1061≤x,y1,y2≤106 ) or ‘3’.
x,y,c,y1,y2x,y,c,y1,y2 are all integers.
Assume the last operation is 3 and it appears only once.
There are at most 150000150000 continuous operations of operation 1 and operation 2.
There are at most 1010 operation 0.
Output For each operation 2, output an integer means the answer . Sample Input 0 1 1000000 1000000 50 1 1000000 999999 0 1 1000000 999999 0 1 1000000 1000000 49 2 1000000 1000000 1000000 2 1000000 1 1000000 0 1 1 1 1 2 1 1 2 1 1 2 2 2 1 1 2 1 2 2 2 2 1 1 2 1 2 1 3 2 2 1 2 2 10 1 2 2 10 2 2 0 1 1 1 1 2 1 1 1 1 1 2 1 2 1 1 2 1 2 2 1 2 1 1 2 1 2 1 1 2 2 1 2 2 10 1 2 2 10 2 2 3 Sample Output 2 3 1 2 2 3 3 1 1 1 1 1 1 1
这个题就是说 给你四种操作 0：清空所有的点 1：在(x,y)处添加一个c颜色的点 2：统计(1,y1)到(x,y2) 这个矩阵里面有多少种不同的颜色 3：退出
因为颜色只有 50 所以考虑开50棵线段树，又因为 50*150000*4 还是会爆，所以缩成一棵，然后发现tle了，因为离线常数太大，考虑在线操作，因为每棵树不超过150000个点，所以完全可以动态开点，利于类似主席树的思想进行操作。 然后这样的空间复杂度 是1.5e5*log(1e6) 1,5e5*个21 完全没问题
*
#include <bits/stdc++.h> using namespace std; int op,X,flag; int T[55],v[3300000],ls[3300000],rs[3300000]; int tot; const int BUF=30000000; char Buf[BUF],*buf=Buf; inline void read(int&a){for(a=0;*buf<48;buf++);while(*buf>47)a=a*10+*buf++-48;} void insert(int &x,int l,int r,int d,int val) { if(!x) { x=++tot; v[x]=val; } if(val<v[x]) v[x]=val; if(l==r) return ; int mid=(l+r)>>1; if(d<=mid) insert(ls[x],l,mid,d,val); else insert(rs[x],mid+1,r,d,val); } int L,R; void query(int x,int l,int r) { if(flag||!x) return ; if(L<=l&&R>=r) { if(v[x]<=X) flag=1; return ; } int mid=(l+r)>>1; if(L<=mid) query(ls[x],l,mid); if(R>mid) query(rs[x],mid+1,r); } int main() { fread(Buf,1,BUF,stdin); for(int i=0;i<=50;i++) T[i]=0; while(1) { read(op); if(op==3) return 0; if(op==0) { for(int i=0;i<=tot;i++) ls[i]=rs[i]=0; for(int i=0;i<=50;i++) T[i]=0; tot=0; } if(op==1) { int x,y,c; read(x),read(y),read(c); insert(T[c],1,1000000,y,x); } if(op==2) { read(X),read(L),read(R); int ans=0; for(int i=0;i<=50;i++) { flag=0; query(T[i],1,1000000); if(flag) ans++; } printf("%d\n",ans ); } } }学了一波cdq分治，其实是把时间当成二分对象，然后递归处理，把1~n进行递归，每层都是n， 一共logn层，线段树查询修改时间也是logn 所以总复杂度是 mlogn*logn 常数比较小，比50个线段树少得多 题解：这道题一共四个维度，我们可以这样分配：x轴排序，时间用cdq分治，y坐标用线段树，颜色用位压缩（64位表示）。
#include <bits/stdc++.h> using namespace std; const int N = 150005; typedef long long ll; struct node { int op; int q[3]; int t; }Q[N],SQ[N]; int b[N*2]; int top; ll sum[N*4]; ll ans[N]; int cmp(node a,node b) { if(a.q[0]==b.q[0]) return a.op<b.op; return a.q[0]<b.q[0]; } void update(int d,int l,int r,int w,int rt,int flag) { if(l==r&&l==d) { if(!flag) sum[rt]|=(1ll<<w); else sum[rt]=0; return ; } int mid=(l+r)>>1; if(d<=mid) update(d,l,mid,w,rt<<1,flag); else update(d,mid+1,r,w,rt<<1|1,flag); if(!flag) sum[rt]=sum[rt<<1]|sum[rt<<1|1]; else sum[rt]=0; } ll query(int L,int R,int l,int r,int rt) { if(L<=l&&R>=r) { return sum[rt]; } ll res=0; int mid=(l+r)>>1; if(L<=mid) res|=query(L,R,l,mid,rt<<1); if(R>mid) res|=query(L,R,mid+1,r,rt<<1|1); return res; } 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,Q[i].q[2],1,0); 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,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(sum,0,sizeof(sum)); 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("%d%d%d",&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(int j=0;j<=50;j++) if(ans[i]&(1ll<<j)) ansha++; printf("%d\n",ansha ); } } return 0; }