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 
     
      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
      
       >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 
     
      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
      
       >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