Color it

Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 132768/132768 K (Java/Others) Total Submission(s): 299    Accepted Submission(s): 60 Problem Description 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. 0  : clear all the points. 1   x   y   c  : add a point which color is  c  at point  (x,y) . 2   x   y1   y2  : count how many different colors in the square  (1,y1)  and  (x,y2) . That is to say, if there is a point  (a,b)  colored  c , that  1≤a≤x  and  y1≤b≤y2 , then the color  c  should be counted. 3  : 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≤50  ), '2 x y1 y2' ( 1≤x,y1,y2≤106  ) or '3'.  x,y,c,y1,y2  are all integers. Assume the last operation is 3 and it appears only once. There are at most  150000  continuous operations of operation 1 and operation 2.  There are at most  10  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 到 x1，纵坐标 y1 到 y2 这块区域内颜色种数

3是结束程序

思路：

这个坐标的范围是 1 到 10^6 ，没法开那么大的线段树，所以我们可以对每种颜色建一个线段上，总共51种颜色，所以建立51棵线段树，由于横坐标固定了一个1，所以我们可以根据纵坐标建立线段树，用来维护对于颜色c，在纵坐标为 y1 的时候，最近的颜色的横坐标是多少，所以每次进一个点的时候，如果这个纵坐标已经有这种颜色了，就更新为横坐标最小的情况，因为确定了是从1开始，所以横坐标小的点总是能被取到。

做法表较特殊 ，用一个root[]数组存每种颜色的根，然后有一个 rson[] 和 lson[]数组，还有最重要的 v[]数组

Update的时候，进来一个节点，每次向左向右跑的时候就对应去到 lson 和 rson ，然后对于每种颜色在每个纵坐标下都会有一个编号，把那个编号作为线段树的编号，存在 v[]里面，存的是最小的横坐标。

查询的时候去查每种颜色，看是否在范围内就可以计数了。

#include<cstdio> #include<cstdio> #include<iostream> #include<algorithm> #include<cstring> using namespace std; #define maxn 1100005 int cnt,lson[maxn * 3],rson[maxn * 3],v[maxn * 3]; int root[55],x1,y1,y2,flag; void Update(int &rot,int l,int r,int x,int y){ int mid = (l + r) >> 1; if(rot == 0){ //如果这个颜色在这个y坐标第一次出现，那么给它一个编号，并且把最近的x赋值 rot = ++cnt; v[rot] = x; } if(v[rot] > x){ // 如果这个颜色的 x 比记录的小，更新最近值 v[rot] = x; } if(l == r){ return ; } if(y <= mid){ Update(lson[rot],l,mid,x,y); }else{ Update(rson[rot],mid + 1,r,x,y); } } void Query(int rot,int l,int r){ int mid = (l + r) >> 1; if(flag || rot == 0){ return ; } if(l >= y1 && r <= y2){ //在y范围内且x在范围内 则表示该颜色存在 if(v[rot] <= x1) flag = 1; return ; } if(y1 <= mid) Query(lson[rot],l,mid); if(y2 >= mid + 1) Query(rson[rot],mid + 1,r); } int main(){ int ans,opt,x,y,c; while(scanf("%d",&opt) != EOF){ if(opt == 3) break; else if(opt == 0){ for(int i = 1;i <= cnt;i++){ lson[i] = rson[i] = 0; } memset(root,0,sizeof(root)); cnt = 0; }else if(opt == 1){ scanf("%d %d %d",&x,&y,&c); Update(root[c],1,maxn,x,y); }else if(opt == 2){ scanf("%d %d %d",&x1,&y1,&y2); ans = 0; for(int i = 0;i <= 50;i++){ flag = 0; Query(root[i],1,maxn); ans += flag; } printf("%d\n",ans); } } return 0; }