线段树,区间修改+区间查询
墨小鳌
2020年02月22日 21:57

题源:poj2777

考点:线段树区间修改+区间查询

题意:L(L<=100000)个单位长的区间可供涂色,初始颜色为1,每次给出可供选择的T(T<=30)种颜色

           有两种操作

                    操作C:将区间[a,b]修改成颜色c

                    操作P:询问区间[a,b]有几种不同颜色

思路:由于T<=30,我们可以采取二进制状态压缩的方法,当前区间的颜色状态用一个int就可以存储下了,对于询问,我们只需要对于区间[a,b]求或(OR)之和就可以了

注意:由于是区间修改,需要用到lazy标记,代码里图方便直接用颜色状态表示了,其实只开一个bool就行

代码:https://www.cnblogs.com/JasonCow/p/12347045.html