首页 > 代码库 > hdu 5023 A Corrupt Mayor's Performance Art(线段树区间更新)
hdu 5023 A Corrupt Mayor's Performance Art(线段树区间更新)
#include<stdio.h> #include<iostream> #include<string.h> #include<algorithm> using namespace std; int tree[5001000],add[5001000]; int color[50]; int n,m; void pushup(int pos) { tree[pos]=tree[pos<<1]|tree[pos<<1|1]; //更新父节点 } void pushdown(int pos) { if(add[pos]) { add[pos<<1]=add[pos]; add[pos<<1|1]=add[pos]; tree[pos<<1]=add[pos]; tree[pos<<1|1]=add[pos]; add[pos]=0; //子节点更新后,父节点的延迟标记去掉 } } void build(int l,int r,int pos) { add[pos]=0; //初始时,所有节点都未标记 if(l==r) { tree[pos]=2; //初始时,颜色为2 return; } int mid=(l+r)/2; build(l,mid,2*pos); build(mid+1,r,2*pos+1); pushup(pos); } void update(int L,int R,int pos,int l,int r,int val) { if(l<=L&&r>=R) { tree[pos]=val; add[pos]=val; return; } pushdown(pos); //向下更新 int mid=(L+R)/2; if(l<=mid) update(L,mid,pos<<1,l,r,val); if(r>mid) update(mid+1,R,pos<<1|1,l,r,val); pushup(pos); } int Query(int L,int R,int pos,int l,int r) { if(l<=L&&r>=R) return tree[pos]; pushdown(pos); int mid=(L+R)/2; if(l>mid) Query(mid+1,R,pos<<1|1,l,r); else if(r<=mid) Query(L,mid,pos<<1,l,r); else return Query(L,mid,pos<<1,l,r)|Query(mid+1,R,pos<<1|1,l,r); } int main() { int i,j,k,a,b,c; char ch[50]; while(scanf("%d%d",&n,&m)!=EOF) { if(n==0||m==0) break; build(1,n,1); for(j=0;j<m;j++) { scanf("%s",ch); if(ch[0]=='P') { scanf("%d%d%d",&a,&b,&c); update(1,n,1,a,b,1<<(c-1)); } else { scanf("%d%d",&a,&b); int ans=Query(1,n,1,a,b); int cnt=0; for(i=1;i<=30;i++) { if(ans&(1<<(i-1))) color[++cnt]=i; } for(i=1;i<cnt;i++) printf("%d ",color[i]); printf("%d\n",color[i]); } } } return 0; }
hdu 5023 A Corrupt Mayor's Performance Art(线段树区间更新)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。