题目链接：hdu 6183 Color it
题意：
在一个二维平面上有n个操作。
1. x y c 在(x,y)这点上添加一个颜色c。
2. x y1 y2 询问二维平面[1,x]~[y1,y2]上有多少不同的颜色。
题解：
由于这题在x轴每次都是询问的[1,x]，所以我们开50棵线段树，对于每种颜色维护每个y坐标的最小x，查询的时候就是区间查询[y1,y2]的最小x是否小于当前查询的x。
这里由于空间有限制，要用最原始版本的线段树，动态开点。
1 #include<bits/stdc++.h> 2 #define F(i,a,b) for(int i=a;i<=b;++i) 3 using namespace std; 4 5 const int M=3e6+7,N=1e6; 6 struct Node{int l,r,v;}T[M]; 7 int tot,rt[51],flag,a,b,c,d; 8 9 void update(int x,int v,int &rt,int l=1,int r=N) 10 { 11 if(!rt)T[rt=++tot]=Node{0,0,v}; 12 if(T[rt].v>v)T[rt].v=v; 13 if(l==r)return; 14 int mid=l+r>>1; 15 if(x<=mid)update(x,v,T[rt].l,l,mid); 16 else update(x,v,T[rt].r,mid+1,r); 17 } 18 19 void ask(int L,int R,int rt,int x,int l=1,int r=N) 20 { 21 if(flag||!rt)return; 22 if(L<=l&&r<=R) 23 { 24 if(T[rt].v<=x)flag=1; 25 return; 26 } 27 int mid=l+r>>1; 28 if(L<=mid)ask(L,R,T[rt].l,x,l,mid); 29 if(R>mid)ask(L,R,T[rt].r,x,mid+1,r); 30 } 31 32 int main(){ 33 while(1) 34 { 35 scanf("%d",&a); 36 if(a==3)break; 37 if(a==0) 38 { 39 F(i,0,50)rt[i]=0; 40 tot=0; 41 } 42 if(a==1) 43 { 44 scanf("%d%d%d",&b,&c,&d); 45 update(c,b,rt[d]); 46 } 47 if(a==2) 48 { 49 scanf("%d%d%d",&b,&c,&d); 50 int ans=0; 51 F(i,0,50) 52 { 53 flag=0; 54 ask(c,d,rt[i],b); 55 ans+=flag; 56 } 57 printf("%d\n",ans); 58 } 59 } 60 return 0; 61 }