Description
【题意】
有L段线段(编号为1~L, (0 <= L <= 1000000)),一开始全部线段是颜色1。
有两种操作:
1、C A B tt :把第A至第B个线段染成第tt种颜色
2、P A B :询问第A至第B个线段有多少种不一样的颜色。
注意:
1、A有可能比B大。
2、颜色的编号<=50;
数据较水,不用担心特殊的情况,按照题解打也能AC,数据强的版本已放在1238
【输入格式】
第一行含有三个整数 L and M (1 <= M <= 100000). M代表操作次数. 下来M行操作
【输出格式】
有询问的时候输出
【样例输入】
2 4
C 1 1 2
P 1 2
C 2 2 2
P 1 2
【样例输出】
2
1
算法思路:
第一题中修改的是一个点,现在修改的是一段,不用线段树,修改也会超时
统计一段里面颜色的种数,也是得用线段树,不然也会超时。
所以这道题体现线段树更加彻底。
这一题的c我们运用一个新东西叫做bitset
需要的头文件
#include<bitset>
定义方法
bitset<你要的大小> bi
赋值
直接像变量一样用就好了
a[x]=1或a[x]=0
与bool的巨大区别
可以用一切运算符,想<<,>>,^,|,&等,和二进制一样
一些常用的函数
bool any( )
是否存在置为1的二进制位?和none()相反
bool none( )
是否不存在置为1的二进制位,即全部为0?和any()相反.
size_t count( )
二进制位为1的个数.
size_t size( )
二进制位的个数
flip()
把所有二进制位逐位取反
set()
把所有二进制位都置为1
set(pos)
把在pos处的二进制位置为1
reset()
把所有二进制位都置为0
count()
获得由多少个1
那么统计颜色怎么办?全局用一个ans,一有颜色就加进ans当中,最后直接count即可。