POJ 2777 Count Color（线段树 + 染色问题）

Description

Input

Output

Sample Input

2 2 4
C 1 1 2
P 1 2
C 2 2 2
P 1 2

Sample Output

2
1

Source

给定一个长度为N(N <= 100000)的数列Si，紧接着Q(Q <= 100000)条操作，操作 形式有两种： 1. "C A B C" 将A到B的数都染成C这种颜色。 2. "P A B" 输出A和B之间不同颜色的数目。

首先要想到的就是线段树，经典的区间维护问题，这里需要用到一个叫懒惰标记的方法，

这样可以大大缩短更新所需要的时间

这里还有一个巧妙地地方，就是区间染色的个数，这个可以用二进制位来解决，最多30种，用

一个int就可以存下，每个位代表一个颜色，区间上的颜色可以取其子区间或和（详细看代码）。

关于懒惰标记：

lazy是一个很经典的思想。所谓lazy，就是懒惰，每次不想做太多，只要插入的区间完

全覆盖了当前结点所管理的区间就不再往下做了，在当前结点上打上一个lazy标记，然

后直接返回。下次如果遇到当前结点有lazy标记的话，直接传递给两个儿子，自己的标

记清空。这样做肯定是正确的。我们以染色为例，可以这样想，如果当前结点和它的子

孙都有lazy标记的话，必定是子孙的先标记，因为如果是自己先标记，那么在访问子孙

的时候，必定会将自己的标记下传给儿子，而自己的标记必定会清空，那么lazy标记也

就不存在了。所以可以肯定，当前的lazy标记必定覆盖了子孙的，所以直接下传即可，

不需要做任何判断