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.
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.
InputThe 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.
OutputFor 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
思路:
有50种颜色,对每一种颜色建一颗线段树维护,动态开点。
第一种操作:使点(x,y)的颜色变为c
第二种:询问(1,y1),(x,y2)两点间的颜色种类数量
我们可以以y轴建线段树,横坐标为值,那么要确定两点之前是否存在某种颜色,只要询问下每个颜色在y1,y2之间最小的值(也就是横坐标).判断下最小值是否小于第二种操作给出的x,如果小于的话就代表两点间存在这种颜色。
实现代码:
#include<bits/stdc++.h> using namespace std; #define ll long long #define mid int m = (l + r) >> 1 const int M = 1e6+10; int n = 1e6,flag=0; int sum[M],ne=0,ls[M],rs[M],rt[100]; void update(int &k,int l,int r,int p,int num){ if(!k){ //如果当前区间未拓展,拓展并赋值 k = ++ne; sum[k] = num; } sum[k] = min(sum[k],num);//当前区间有值,更新下最小值 if(l == r) return ; mid; if(p <= m) update(ls[k],l,m,p,num); else update(rs[k],m+1,r,p,num); } void query(int k,int L,int R,int l,int r,int up){ if(!k||flag) return ; if(L <= l&&R >= r){ if(sum[k]<=up) flag = 1; return; } mid; if(L <= m) query(ls[k],L,R,l,m,up); if(R > m) query(rs[k],L,R,m+1,r,up); return ; } void init(){ memset(rt,0,sizeof(rt)); memset(sum,0,sizeof(sum)); memset(ls,0,sizeof(ls)); memset(rs,0,sizeof(rs)); ne = 0; } int main() { int op,x,y,z; while(~scanf("%d",&op)){ if(op == 0) init(); else if(op == 1){ scanf("%d%d%d",&x,&y,&z); update(rt[z],1,n,y,x); } else if(op == 2){ scanf("%d%d%d",&x,&y,&z); int ans = 0 ; for(int i = 0;i <= 50;i ++){ flag = 0; query(rt[i],y,z,1,n,x); if(flag) ans++; } printf("%d\n",ans); } else return 0; } return 0; }