Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 100000/100000 K (Java/Others)
Total Submission(s): 1866 Accepted Submission(s): 650
#include<stdio.h> #include<algorithm> #include<math.h> #include<iostream> using namespace std; const int MAXSIZE = 1000000; int sum; struct Tree{ int cover; int color; int l,r; }tree[MAXSIZE<<2]; void pushUp(int idx){ tree[idx].color = tree[idx<<1].color|tree[idx<<1|1].color; } void pushDown(int i){ if(tree[i].cover){ tree[i<<1].color=tree[i].color ; tree[i<<1|1].color=tree[i].color; tree[i<<1].cover = tree[i<<1|1].cover = 1; tree[i].cover = 0; } } void build(int l,int r,int idx){ tree[idx].l = l; tree[idx].r = r; tree[idx].color =2; //这个题和hdu 2777 没什么不同,就是要初始化为2 The wall‘s original color was color 2. tree[idx].cover = 1; if(l==r) return; int mid = (l+r)>>1; build(l,mid,idx<<1); build(mid+1,r,idx<<1|1); pushUp(idx); } void update(int l,int r,int idx,int value){ if(tree[idx].l>=l&&tree[idx].r<=r){ tree[idx].color = value; tree[idx].cover = 1; return; } pushDown(idx); int mid = (tree[idx].l+tree[idx].r)>>1; if(r<=mid) update(l,r,idx<<1,value); else if(l>mid) update(l,r,idx<<1|1,value); else { update(l,mid,idx<<1,value); update(mid+1,r,idx<<1|1,value); } pushUp(idx); } void query(int l,int r,int idx){ if(tree[idx].l>=l&&tree[idx].r<=r){ sum|=tree[idx].color; return; } if(tree[idx].cover) { sum|=tree[idx].color; return; } int mid = (tree[idx].l+tree[idx].r)>>1; if(r<=mid) query(l,r,idx<<1); else if(l>mid) query(l,r,idx<<1|1); else { query(l,mid,idx<<1); query(mid+1,r,idx<<1|1); } } void solve(){ int a[30]; //printf("%d\n",sum); int k=0,t=0; while(sum){ if(sum&1) a[k++] = t+1; t++; sum = sum>>1; } for(int i=0;i<k-1;i++) printf("%d ",a[i]); printf("%d\n",a[k-1]); } int main() { int n,m; while(scanf("%d%d",&n,&m),n+m){ build(1,n,1); while(m--){ char s[5]; scanf("%s",s); if(s[0]==‘P‘){ int a,b,c; scanf("%d%d%d",&a,&b,&c); update(a,b,1,1<<(c-1)); }else{ int a,b; scanf("%d%d",&a,&b); sum = 0; query(a,b,1); solve(); } } } return 0; }
原文:http://www.cnblogs.com/liyinggang/p/5304361.html