題目位址:http://acm.hdu.edu.cn/showproblem.php?pid=5023
思路:用一30位數每一位表示有某個顔色,使用線段樹進行區間修改與查詢。最後某位為1,則存在該種顔色。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define root 1,maxn,1
#define debu
using namespace std;
typedef long long LL;
const int maxn=1e6+50;
int n,Q;
int add[maxn<<2],sum[maxn<<2];
void PushUp(int rt)
{
sum[rt]=sum[rt<<1]|sum[rt<<1|1];
}
void PushDown(int rt)
{
if(add[rt])
{
add[rt<<1]=add[rt];
add[rt<<1|1]=add[rt];
sum[rt<<1]=add[rt];
sum[rt<<1|1]=add[rt];
add[rt]=0;
}
}
void build(int l,int r,int rt)
{
add[rt]=0;
if(l==r)
{
sum[rt]=2;
return ;
}
int m=(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);
return ;
}
PushDown(rt);
int m=(l+r)>>1;
if(L<=m) Update(L,R,c,lson);
if(m<R) Update(L,R,c,rson);
PushUp(rt);
}
int Query(int L,int R,int l,int r,int rt)
{
if(L<=l&&r<=R) return sum[rt];
PushDown(rt);
int m=(l+r)>>1;
int ret=0;
if(L<=m) ret|=Query(L,R,lson);
if(m<R) ret|=Query(L,R,rson);
return ret;
}
int main()
{
#ifdef debug
freopen("in.in","r",stdin);
#endif // debug
while(scanf("%d%d",&n,&Q)!=EOF&&(n||Q))
{
getchar();
memset(add,0,sizeof(add));
memset(sum,0,sizeof(sum));
build(root);
while(Q--)
{
char ch;
scanf("%c",&ch);
if(ch=='P')
{
int l,r,x;
scanf("%d%d%d",&l,&r,&x);
getchar();
Update(l,r,x,root);
}
else
{
int l,r;
scanf("%d%d",&l,&r);
getchar();
int ans=Query(l,r,root);
int flag=1;
for(int i=0; i<30; i++)
{
if((ans>>i)&1)
{
if(flag)
{
printf("%d",i+1);
flag=0;
}
else printf(" %d",i+1);
}
}
printf("\n");
}
}
}
return 0;
}