poj2777Count Color(线段树，段更新，段查询用map函数)

#include<stdio.h>#include<map>#include<iostream>using namespace std;#define N 100000struct node{int type,b;}tree[4*N];void biulde(int l,int r,int k){int m=(l+r)/2;tree[k].b=1; tree[k].type=1;if(l==r) return ;biulde(l,m,k*2); biulde(m+1,r,k*2+1);}int L,R,C;void updataColor(int l,int r,int k){int m=(l+r)/2;if(tree[k].b&&tree[k].type==C) return ;if(L<=l&&r<=R){tree[k].type=C; tree[k].b=1;return ;}if(tree[k].b){tree[k*2].b=tree[k*2+1].b=1;tree[k*2].type=tree[k*2+1].type=tree[k].type;}if(L<=m) updataColor(l,m,k*2);if(R>m) updataColor(m+1,r,k*2+1);tree[k].b=0;}int typesum;map<int,int>types;void count_typesum(int l,int r,int k){int m=(l+r)/2;if(tree[k].b){if(types[tree[k].type]==0) typesum++; types[tree[k].type]=1;return ;}if(L<=m) count_typesum(l,m,k*2);if(R>m) count_typesum(m+1,r,k*2+1);}int main(){int m,n,T;char c[2];scanf("%d%d%d",&n,&T,&m);biulde(1,n,1);while(m--){scanf("%s%d%d",c,&L,&R);if(c[0]=='C'){scanf("%d",&C);updataColor(1,n,1);}else{types.clear(); typesum=0;count_typesum(1,n,1);printf("%d\n",typesum);}}}