1. 题目

传送门= ̄ω ̄=
题意:一条很长(L)的画板(初始颜色为1),有T种颜色,O个操作;每次操作将一个区间刷成一种颜色,或者查询一个区间内所含的颜色数。

其中L<=1e5,T<=30,O<=1e5

TMD有多组数据

2. 题解

显然线段树
然后因为颜色数不大于30,可以用位运算(int就够了)
把一个区间覆盖为颜色i就让这个区间的值变为1<<i

然后区间求和就和普通线段树一样,这不过这里是求区间的或和的二进制下1的位数

至于求一个数的二进制下1的位数,用lower_bound函数可以快速求得。

用指针线段树会TLE,因为要清空树,耗时间,而且动态申请内存也慢。

代码: