Problem1100--[视频]线段树2(统计不同颜色)

1100: [视频]线段树2(统计不同颜色)

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 4  Solved: 2
[Status] [Submit] [Creator:]

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即可。

HINT

Source/Category