人生中第一次写线段树，想想还有点小激动=.=
其实开始照着一份代码敲本地就RE了。。然后一怒之下copy模板：数据结构---各种树模板 持续更新···
关于pushDown的问题想了好久，其实就是父节点的值改变了，要更新其子节点，因为子节点的区间并起来就是父节点表示的区间，这一篇blog写的比较详细：一步一步理解线段树
这一题就是用二进制数表示染了哪一种颜色，query的时候，因为分别对左右子数递归，因此返回值取 或 运算就可以了，最后再用位运算判断一下哪几位是1。
#include<iostream>
#include<stdio.h>
#include<cstdio>
#include<stdlib.h>
#include<vector>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include <ctype.h>
using namespace std;
//hdu 5023
const int maxn=1000100;
int N;
int Q;
#define lson l , mid , rt << 1
#define rson mid + 1 , r , rt << 1 | 1
#define LL int
/* Node Begin */
LL add[maxn<<2];
LL sum[maxn<<2];
/* Node End */
void PushUp(int rt) {
sum[rt] = sum[rt<<1] | sum[rt<<1|1];
//原先的模板求的是区间和，所以是sum[rt] = sum[rt<<1] + sum[rt<<1|1];
//此处是求区间内一共多少种颜色，所以是 或 的关系
}
void PushDown(int rt,int m) {
if (add[rt]) {
add[rt<<1] = add[rt];
//上一层为[a,c],下一层为[a,b][b+1,c]，当上一层延迟标记为x时，下一层对应的儿子的标记也会变成x（因为[a,b]+[b+1,c]=[a,c]）
add[rt<<1|1] = add[rt];
sum[rt<<1] = sum[rt] ;
sum[rt<<1|1] = sum[rt];
//上一层[a,c]被染成y,则下一层对应的子区间颜色也变成了y
// sum[rt<<1] = add[rt] ; //all is ok,因为染色时add[i]和sum[i]的赋值相同
// sum[rt<<1|1] = add[rt];
add[rt] = 0;
// 原先的模板如下，是因为之前求的是区间和，父节点的值改变后要再更新子节点。
// 因为子节点可能被多次延迟标记又没有向下传递 ，所以是 “+=”
// add[rt<<1] += add[rt];
// add[rt<<1|1] += add[rt];
// sum[rt<<1] += add[rt] * (m - (m >> 1));
// sum[rt<<1|1] += add[rt] * (m >> 1);
}
}
void build(int l,int r,int rt) {
add[rt] = 0;
if (l == r) {
sum[rt]=2;
return ;
}
int mid = (l + r) >> 1;
build(lson);
build(rson);
PushUp(rt);
}
void update(int L,int R,int c,int l,int r,int rt) {
if (L <= l && r <= R) {
add[rt] =1<<(c-1);
sum[rt] =1<<(c-1);
//求区间和时，sum如果为非叶子节点，增加量则为c*区间的节点数
//add[rt] += c;
//sum[rt] += (LL)c * (r - l + 1);
return ;
}
PushDown(rt , r - l + 1);
int mid = (l + r) >> 1;
if (L <= mid) update(L , R , c , lson);
if (mid < R) update(L , R , c , rson);
PushUp(rt);
}
LL query(int L,int R,int l,int r,int rt) {
if (L <= l && r <= R) {
return sum[rt];
}
PushDown(rt , r - l + 1);
int mid = (l + r) >> 1;
LL ret = 0;
if (L <= mid) ret |= query(L , R , lson);
if (mid < R) ret |= query(L , R , rson);
//如果是求区间和，则是ret += query(L , R , lson); 此处是颜色种类数，是或的关系
return ret;
}
int main()
{
freopen("input.txt","r",stdin);
// freopen("data.txt","r",stdin);
// freopen("out1.txt","w",stdout);
int a,b,c=0;
while(true)
{
scanf("%d %d",&N,&Q);
if(N==0&&Q==0) break;
build(1,N,1);
while(Q--)
{
char s[2];
scanf("%s",&s);
if(s[0]=='P')
{
scanf("%d %d %d",&a,&b,&c);
update(a,b,c,1,N,1);
}
else if(s[0]=='Q')
{
scanf("%d %d",&a,&b);
int ans=query(a,b,1,N,1);
int flg=1;
for(int i=0;i<31;i++)
{
int x=ans&(1<<i);
if(x)
{
if(flg)
{
printf("%d",i+1);
flg=0;
}
else printf(" %d",i+1);
}
}
printf("\n");
}
}
}
return 0;
}