参考：https://www.cnblogs.com/dongsheng/archive/2012/08/08/2628845.html
1 /* 2 功能Function Description: POJ 2777 线段树 3 开发环境Environment: DEV C++ 4.9.9.1 4 技术特点Technique: 5 版本Version: 6 作者Author: 可笑痴狂 7 日期Date: 20120808 8 备注Notes: 9 题意： 10 给定一个长度为N(N <= 100000)的数列Si，紧接着Q(Q <= 100000)条操作，操作 11 形式有两种： 12 1. "C A B C" 将A到B的数都染成C这种颜色。 13 2. "P A B" 输出A和B之间不同颜色的数目。 14 15 16 解法：-------转 17 线段树（染色问题） 18 19 思路： 20 一看到数据量就可以首先确定是线段树了，经典的区间染色问题，涉及到区间的 21 更新和询问，和pku 3468 类似，巧妙运用lazy思想。就是每次更新区间段的时候延迟 22 更新，只是在完全覆盖的区间打上一个lazy标记。这题的询问是求区间段中不同颜色的 23 数量，因为颜色数不多只有30种，可以巧妙运用二进制位运算，用一个int就可以表示 24 当前区间段的颜色情况。比如1001表示有两种颜色，如果左子树的当前颜色情况是101 25 ，而右子树的颜色情况是011，那么父亲的颜色情况就是两者的位或，这样就可以避免 26 掉重复的情况。 27 再来谈谈lazy思想。做了这么多的线段树，应该总结一下，lazy是一个很经典的思 28 想。所谓lazy，就是懒惰，每次不想做太多，只要插入的区间完全覆盖了当前结点所管 29 理的区间就不再往下做了，在当前结点上打上一个lazy标记，然后直接返回。下次如果 30 遇到当前结点有lazy标记的话，直接传递给两个儿子，自己的标记清空。这样做肯定是 31 正确的。我们以染色为例，可以这样想，如果当前结点和它的子孙都有lazy标记的话， 32 必定是子孙的先标记，因为如果是自己先标记，那么在访问子孙的时候，必定会将自己 33 的标记下传给儿子，而自己的标记必定会清空，那么lazy标记也就不存在了。所以可以 34 肯定，当前的lazy标记必定覆盖了子孙的，所以直接下传即可，不需要做任何判断。当 35 然，这是染色问题，是直接赋值的，如果像pku 3468那样，每次是区间加和，则传递标 36 记的时候不能简单的赋值，必须累加，这是显而易见的。 37 */ 38 39 40 //这是仿照别人写的AC代码 41 #include<stdio.h> 42 43 struct node 44 { 45 int lc,rc; 46 int state; //用二进制的每一位中的1的个数来标记颜色的个数，该数并不是颜色个数，而代表该区间的颜色集合，int有32位，每一位表示一种颜色，足够表示30种颜色 47 int id; //标记状态看是否被完全覆盖 48 }tree[300010]; 49 50 51 void build(int s,int t,int T) 52 { 53 int mid; 54 tree[T].lc=s; 55 tree[T].rc=t; 56 if(s==t) 57 return ; 58 mid=(s+t)>>1; 59 build(s,mid,T<<1); 60 build(mid+1,t,(T<<1)|1); //位运算，等价于build(mid+1,t,(T<<1)+1); 61 } 62 63 void insert(int s,int t,int T,int value) //从s到t涂上颜色value，从T节点开始查找 64 { 65 int mid; 66 if(tree[T].lc==s&&tree[T].rc==t) //说明涂色范围正好完全覆盖T所包含的区域，直接更新颜色信息，下边的节点不用管 67 { 68 tree[T].id=1; //标记为完全覆盖 69 tree[T].state=1<<(value-1); //不同的颜色用2进制不同位上的1表示，如颜色1为最右位的1 70 return ; 71 } 72 if(tree[T].id) //说明T是完全覆盖的，更新T孩子节点的信息 73 { 74 tree[T].id=0; 75 tree[T<<1].id=tree[(T<<1)|1].id=1; 76 tree[T<<1].state=tree[(T<<1)|1].state=tree[T].state;//子区间颜色与父区间颜色相同 77 } 78 mid=(tree[T].lc+tree[T].rc)>>1; 79 if(t<=mid) 80 insert(s,t,T<<1,value); 81 else if(s>mid) 82 insert(s,t,(T<<1)|1,value); 83 else 84 { 85 insert(s,mid,T<<1,value); 86 insert(mid+1,t,(T<<1)|1,value); 87 } 88 tree[T].state=(tree[T<<1].state)|(tree[T<<1|1].state);// 等同于把颜色数相加，排除了相同颜色的重复计算 89 if(tree[T<<1].id&&tree[(T<<1)|1].id&&tree[T<<1].state==tree[(T<<1)|1].state)//相当于父区间也全覆盖 90 tree[T].id=1; 91 } 92 93 int qurry(int s,int t,int T) //从T节点开始查询区间s到t颜色的个数 94 { 95 int mid; 96 if(tree[T].lc==s&&tree[T].rc==t) 97 return tree[T].state; 98 if(tree[T].id) //减枝----说明T是全覆盖的直接返回状态值即可 99 return tree[T].state; 100 mid=(tree[T].lc+tree[T].rc)>>1; 101 if(t<=mid) 102 return qurry(s,t,T<<1); 103 else if(s>mid) 104 return qurry(s,t,(T<<1)|1); 105 else 106 return qurry(s,mid,T<<1)|qurry(mid+1,t,(T<<1)|1); 107 } 108 109 int main() 110 { 111 int i,j,k,color,t,num,len,m; 112 char cmd[2]; 113 while(scanf("%d%d%d",&len,&color,&m)!=EOF) 114 { 115 build(1,len,1); 116 tree[1].state=1; 117 tree[1].id=1; 118 while(m--) 119 { 120 scanf("%s",cmd); 121 if(cmd[0]=='C') 122 { 123 scanf("%d%d%d",&i,&j,&k); 124 if(i>j) 125 { 126 t=i; 127 i=j; 128 j=t; 129 } 130 insert(i,j,1,k); 131 } 132 else 133 { 134 scanf("%d%d",&i,&j); 135 if(i>j) 136 { 137 t=i; 138 i=j; 139 j=t; 140 } 141 k=qurry(i,j,1); 142 num=0; 143 for(i=0;i<color;++i) 144 if(k&(1<<i)) 145 ++num; 146 printf("%d ",num); 147 } 148 } 149 } 150 return 0; 151 }