poj 2777-Count Color链接：http://poj.org/problem?id=2777
题意是说有一段长为lcm的线段,每段的长度为1cm总共有t种颜色可以用来给它涂色，我们会随时改变某个区间的颜色，并且询问这个区间内共有多少种不同的颜色
典型的线段树问题，这其实也体现出了线段树比树状数组比起来的优势，所能统计的信息比树状数组要多，用起来更加灵活。
View Code
1 #include<stdio.h>
2 #include<string.h>
3 #define MAX 450000
4 struct node
5 {
6 int l,r;
7 int color;
8 int mid;
9 }s[MAX];
10 bool c[31];
11 void bulid(int l,int r,int id)
12 {
13 s[id].l=l;
14 s[id].r=r;
15 s[id].color=1;
16 s[id].mid=(l+r)>>1;
17 if(l==r)
18 return;
19 bulid(l,s[id].mid,id<<1);
20 bulid(s[id].mid+1,r,id<<1|1);
21 }
22 void update(int l,int r,int color,int id)
23 {
24 if(s[id].l==l&&s[id].r==r)
25 {
26 s[id].color=color;
27 return;
28 }
29 if(s[id].color==color)
30 return;
31 if(s[id].color>0)//只把颜色涂在叶子节点上
32 {
33 s[id<<1].color=s[id<<1|1].color=s[id].color;
34 s[id].color=0;
35 }
36 if(r<=s[id].mid)
37 update(l,r,color,id<<1);
38 else if(l>s[id].mid)
39 update(l,r,color,id<<1|1);
40 else
41 {
42 update(l,s[id].mid,color,id<<1);
43 update(s[id].mid+1,r,color,id<<1|1);
44 }
45 }
46
47 void query(int l,int r,int id)
48 {
49 if(s[id].color>0)
50 {
51 c[s[id].color]=true;
52 return;
53 }
54 if(r<=s[id].mid)
55 query(l,r,id<<1);
56 else if(l>s[id].mid)
57 query(l,r,id<<1|1);
58 else
59 {
60 query(l,s[id].mid,id<<1);
61 query(s[id].mid+1,r,id<<1|1);
62 }
63 }
64
65 int main()
66 {
67 int l,t,o;
68 int i;
69 char ch[5];
70 int x,y,z;
71 while(scanf("%d%d%d",&l,&t,&o)!=EOF)
72 {
73 bulid(1,l,1);
74 while(o--)
75 {
76 scanf("%s",ch);
77 if(ch[0]=='C')
78 {
79 scanf("%d%d%d",&x,&y,&z);
80 update(x,y,z,1);
81 }
82 else
83 {
84 int sum=0;
85 scanf("%d%d",&x,&y);
86 memset(c+1,0,sizeof(bool)*t);
87 query(x,y,1);
88 for(i=1;i<=t;i++)
89 if(c[i])
90 sum++;
91 printf("%d\n",sum);
92 }
93 }
94 }
95 return 0;
96 }