Link: http://acm.hdu.edu.cn/showproblem.php?pid=5023
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
typedef __int64 LL;
typedef unsigned int UINT;
const int maxn = 1e6 + ; #define LEFT(a,b) ((a) << (b))
#define RIGHT(a,b) ((a) >> (b)) struct node
{
UINT c,num;
int l,r;
node() {}
node(const int t_l,const int t_r,const UINT t_c,const UINT t_num)
{
l = t_l,r = t_r;
c = ( << (t_c - ));
num = t_num;
}
}tree[*maxn]; void Init(const int p)
{
if(tree[p].l == tree[p].r) return ;
int mid = RIGHT(tree[p].l + tree[p].r,);
tree[LEFT(p,)] = node(tree[p].l,mid,,);
tree[LEFT(p,)+] = node(mid+,tree[p].r,,);
Init(LEFT(p,));
Init(LEFT(p,)+);
}
void paste(const int p,const int t_l,const int t_r,const UINT t_c)
{
if(t_l > t_r) return ;
if(t_l == tree[p].l && t_r == tree[p].r)
{
tree[p].c = t_c;
tree[p].num = ;
return ;
}
int mid = (tree[p].l + tree[p].r) / ;
/*
如果该段区间只有一种颜色，则要先把该段区间里的目标区间意外的区间涂成原来的颜色
*/
if( == tree[p].num)
{
paste(LEFT(p,),tree[p].l,mid,tree[p].c);
paste(LEFT(p,)+,mid+,tree[p].r,tree[p].c);
/*
if(t_r <= mid) paste(LEFT(p,1)+1,mid+1,tree[p].r,tree[p].c);
else if(t_l <= mid && t_r > mid)
{
paste(LEFT(p,1),tree[p].l,t_l-1,tree[p].c);
paste(LEFT(p,1)+1,t_r+1,tree[p].r,tree[p].c);
}
else if(t_l > mid) paste(LEFT(p,1),tree[p].l,mid,tree[p].c);
*/
}
if(t_r <= mid) paste(LEFT(p,),t_l,t_r,t_c);
else if(t_l <= mid && t_r > mid)
{
paste(LEFT(p,),t_l,mid,t_c);
paste(LEFT(p,)+,mid+,t_r,t_c);
}
else if(t_l > mid) paste(LEFT(p,)+,t_l,t_r,t_c); tree[p].c = tree[LEFT(p,)].c | tree[LEFT(p,)+].c;
tree[p].num = ;
for(int i = ;i <= ;i++)
if(tree[p].c & ( << i))
tree[p].num++;
} void quire(const int p,const int t_l,const int t_r,UINT& t_c)
{
if( == tree[p].num || (tree[p].l == t_l && tree[p].r == t_r))
{
t_c |= tree[p].c;
return ;
}
int mid = (tree[p].l + tree[p].r) / ;
if(t_r <= mid) quire(LEFT(p,),t_l,t_r,t_c);
else if(t_l <= mid && t_r > mid)
{
quire(LEFT(p,),t_l,mid,t_c);
quire(LEFT(p,)+,mid+,t_r,t_c);
}
else if(t_l > mid) quire(LEFT(p,)+,t_l,t_r,t_c);
}
void print()
{
for(int i = ;i <= ;++i)
printf("%d ",tree[i].c);
puts("");
for(int i = ;i <= ;i++)
printf("%d ",tree[i].num);
puts("");
}
int main()
{
// freopen("in.txt","r",stdin);
int n,m;
while(scanf("%d%d",&n,&m),m+n)
{
tree[] = node(,n,,);
Init();
char oper[];
while(m--)
{
scanf("%s",oper);
if('P' == oper[])
{
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
paste(,x,y, << (c - ));
// print();
}
else
{
int x,y;
UINT t_c = ;
scanf("%d%d",&x,&y);
quire(,x,y,t_c);
bool flag = false;
for(int i = ;i <= ;++i)
if(t_c & ( << i))
{
if(flag) printf(" ");
flag = true;
printf("%d",i+);
}
if(flag) puts("");
// print();
}
}
}
return ;
}