HDu 5029 Relief grainセグメントツリー
2793 ワード
<pre style="font-family: 'Courier New';"><pre name="code" class="html">// [1 , n]
// 2
//p a b c
// [a,b] c
//q a b
// [a,b]
// 30
//
//
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std ;
const int maxn = 1e6+10 ;
#define left v<<1
#define right v<<1|1
struct node
{
int x ;
int op ;
int l , r ;
}tree[maxn<<2] ;
void build(int l , int r , int v)
{
tree[v].l = l ;
tree[v].r = r ;
tree[v].op = 0 ;
tree[v].x = 1<<2 ;
if(l == r)
return ;
int mid = (l + r) >> 1 ;
build(l , mid , left) ;
build(mid+1 , r , right) ;
}
void push_down(int v)
{
if(tree[v].op)
{
tree[left].x = tree[right].x = 1<<tree[v].op ;
tree[left].op = tree[right].op = tree[v].op ;
tree[v].op = 0 ;
}
}
void update(int l , int r ,int v , int co)
{
if(l <= tree[v].l && tree[v].r <= r)
{
tree[v].x = 1<<co ;
tree[v].op = co ;
return ;
}
push_down(v) ;
int mid = (tree[v].l + tree[v].r) >> 1 ;
if(l <= mid)update(l , r , left , co) ;
if(r > mid)update(l , r , right ,co) ;
tree[v].x = tree[left].x|tree[right].x ;
}
int query(int l , int r , int v)
{
if(l <= tree[v].l && tree[v].r <= r)
return tree[v].x ;
push_down(v) ;
int mid = (tree[v].l + tree[v].r) >> 1 ;
int ans = 0 ;
if(l <= mid)ans |= query(l , r , left) ;
if(r > mid)ans |= query(l , r , right) ;
tree[v].x = tree[left].x|tree[right].x ;
return ans ;
}
int main()
{
//freopen("in.txt" , "r" , stdin) ;
int n , m ;
while(scanf("%d%d" , &n , &m) && (n+m))
{
build(1 , n , 1) ;
char ch[5] ;
while(m--)
{
scanf("%s" , ch) ;
int a , b , c ;
if(ch[0] == 'P')
{
scanf("%d%d%d" , &a , &b , &c) ;
update(a , b , 1 , c) ;
}
else if(ch[0] == 'Q')
{
scanf("%d%d" , &a , &b) ;
int sum = query(a , b , 1) ;
int ans = 0 ;
int flag = 0 ;
for(int i = 1;i <= 30;i++)
if(sum&(1<<i))
{
if(flag)printf(" ");
printf("%d" , i) ;
flag = 1 ;
}
puts("") ;
}
}
}
return 0 ;
}