http://poj.org/problem?id=2777
又是一个区间染色问题，和一般的区间染色问题有点点不同，在于这题的线段范围比较大，如果采用cover域表示法的话会超时。
所谓cover域表示法，即当cover值为-1时，表示该线段的颜色为混合色，要求的具体答案必须向下查找，直到找到cover不为-1的子区间。
但是cover表示法也不错，因为我们有时候会别无选择。下面会为大家进行比较。先看这题的题解！
这题虽然线段范围很大，但是我们注意到所用到的颜色最多只有30中，如果采用二进制压缩法的话，一个int 型数据即可以表示出所有的颜色(例如：1001表示了两种颜色，第一种和第四种) 。为线段树添加一个color域，用于表示该线段上有哪些颜色，我们注意到颜色已经压缩成了二进制，那么某区间的颜色便等于它左右两子区间的 ‘或’操作值！采用lazy思想，标记哪些线段是单色的，是单色的，我们便往下传递，最后回溯，利用或操作跟新线段树，这样便大大的剩下了时间！
View Code
1 #include<iostream>
2 #include<string>
3 #include<algorithm>
4 using namespace std;
5
6 struct node
7 {
8 int l;
9 int r;
10 int color;
11 int lazy; //lazy为1表示为颜色需要向下传递
12 };
13
14 node tree[500000];
15 int n,t,m;
16
17 void build(int i,int l,int r)
18 {
19 tree[i].l=l;
20 tree[i].r=r;
21 tree[i].color=1; //题目初始颜色为1
22 tree[i].lazy=0;
23 if(l==r)
24 return;
25 int mid=(l+r)/2;
26 build(2*i,l,mid);
27 build(2*i+1,mid+1,r);
28 }
29
30 void updata(int i,int l,int r,int w)
31 {
32 if(tree[i].l>r || tree[i].r<l)
33 return;
34 if(tree[i].l>=l && tree[i].r<=r)
35 {
36 tree[i].color=w; //完全覆盖，将新颜色覆盖旧颜色
37 tree[i].lazy=1; //同时标记该线段为单色
38 return;
39 }
40 if(tree[i].lazy) //该线段为单色，需要向下传递
41 {
42 tree[2*i].color=tree[2*i+1].color=tree[i].color;
43 tree[2*i].lazy=tree[2*i+1].lazy=1;
44 tree[i].lazy=0;
45 }
46 updata(2*i,l,r,w);
47 updata(2*i+1,l,r,w);
48 tree[i].color=tree[2*i].color|tree[2*i+1].color; //回缩跟新
49 }
50
51 int ans;
52 void find(int i,int l,int r)
53 {
54 if(tree[i].l>r || tree[i].r<l)
55 return;
56 if(tree[i].l>=l && tree[i].r<=r)
57 {
58 ans=ans|tree[i].color;
59 return;
60 }
61 if(tree[i].lazy) //该线段为单色，需要向下传递
62 {
63 tree[2*i].color=tree[2*i+1].color=tree[i].color;
64 tree[2*i].lazy=tree[2*i+1].lazy=1;
65 tree[i].lazy=0;
66 }
67 find(2*i,l,r);
68 find(2*i+1,l,r);
69 }
70
71 void print(int x)
72 {
73 int ans=0;
74 while(x)
75 {
76 x-=(x&(-x));
77 ans++;
78 }
79 printf("%d\n",ans);
80 }
81
82 int main()
83 {
84 int a,b,w,i;
85 char c;
86 freopen("in.txt","r",stdin);
87 while(scanf("%d%d%d",&n,&t,&m)!=EOF)
88 {
89 build(1,1,n);
90 for(i=0;i<m;i++)
91 {
92 getchar();
93 scanf("%c",&c);
94 if(c=='C')
95 {
96 scanf("%d%d%d",&a,&b,&w);
97 if(a>b) //恶心的地方，Wa了好多次
98 swap(a,b);
99 updata(1,a,b,1<<(w-1)); //颜色压缩
100 }
101 else
102 {
103 scanf("%d%d",&a,&b);
104 if(a>b)
105 swap(a,b);
106 ans=0;
107 find(1,a,b);
108 print(ans);
109 }
110 }
111 }
112 return 0;
113 }
这样，我们便顺利的A掉了这题。可是回头想想，这样的方法虽然快，可并不通用，因为二进制的压缩数目毕竟有限。如果题目涉及到了10000种颜色，那还怎么压缩？那就只能用cover域来标记了。不过那样的题目线段范围一定会合理的，不然还让人怎么活？~~