点击打开链接
题意：把区间（l，r）图上某种颜色 颜色会覆盖, 询问区间(L,R)被图上那些种类颜色
思路: 第一步很简单就用线段树中区间更新Set操作修改(l,r)的颜色 第二步询问（L，R)被图上那种颜色时 由于颜色种类<=30 && 父节点肯定包含子节点有的颜色 所以父节点和字节的的关系为或的关系 ，把要图第i种颜色 变为30为二进制数 第i位为1代表包含第i种颜色
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> using namespace std; const int M=1e7+20; long long state[M*4],lazy[M*4];//lazy标记 struct node{ int l,r; int mid() { return (l+r)>>1; } }seg[M<<2]; void pushup(int rt) { state[rt]=state[rt<<1]|state[rt<<1|1];//只要小区间某位为1 则大区间某位肯定也有1 :为或关系 } void build(int l,int r,int rt) { seg[rt].l=l; seg[rt].r=r; lazy[rt]=0; if(l==r) { state[rt]=2;//初始颜色为2 即二进制10 return; } int m=seg[rt].mid(); build(l,m,rt<<1); build(m+1,r,rt<<1|1); pushup(rt); } void Pushdown(int rt) { if(lazy[rt]) { lazy[rt<<1]=lazy[rt];//传递lazy标记 lazy[rt<<1|1]=lazy[rt]; state[rt<<1]=lazy[rt];//改变子区间的颜色 state[rt<<1|1]=lazy[rt]; lazy[rt]=0;//更新后取消lazy标记 } } void update(long long c,int l,int r,int rt) { if(seg[rt].l==l&&seg[rt].r==r) { state[rt]=c;// //把(l,r)中的元素都替换成c lazy[rt]=c;//先不更新子节点 lazy标记 return; } //要分解区间时 把以前没更新的先更新 Pushdown(rt); int m=seg[rt].mid(); //要更新的在节点左边 if(r<=m) { update(c,l,r,rt<<1); } else if(l>m) { update(c,l,r,rt<<1|1); } else//要更新的横跨中点 { update(c,l,m,rt<<1); update(c,m+1,r,rt<<1|1); } pushup(rt); } long long query(int l,int r,int rt) { if(l==seg[rt].l&&r==seg[rt].r)//完全包含 { return state[rt]; } //要用到子区间 Pushdown(rt); int m=seg[rt].mid(); long long res=0; //分解区间 if(r<=m) { res|=query(l,r,rt<<1); } else if(l>m)//所查询区间在右半段 { res|=query(l,r,rt<<1|1); } else//l<m<r<tree[rt].r { res|=query(l,m,rt<<1); res|=query(m+1,r,rt<<1|1); } return res; } int main() { int n,q; while(cin>>n>>q&&(n+q)) { build(1,n,1); while(q--) { int l,r; long long val; char c; cin>>c; if(c=='P') { scanf("%d%d%lld",&l,&r,&val); //30种颜色 可以状压 // 这样sum中：第i位为1 则该区间有图上第i种颜色 //图第i种颜色 则表示为1<<(val-1) val=1<<(val-1); update(val,l,r,1); } if(c=='Q') { int ans[35]; int cnt=0; int l,r; scanf("%d%d",&l,&r); long long s=query(l,r,1); for(int i=0;i<30;i++) { if(s&(1<<i)) { ans[++cnt]=1+i;//第i位为1 则有第i种颜色 } } for(int i=1;i<=cnt;i++) { printf("%d",ans[i]); if(i<cnt) cout<<" "; else cout<<endl; } } } } return 0; }