HDU 5023 A Corrupt Mayor's Performance Art（线段树区间更新）

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<iostream>
  4 #include<algorithm>
  5 using namespace std;
  6 const int maxn = 1000005;
  7 struct node
  8 {
  9     int l,r,c,tot;
 10     void Node(int l1,int r1,int c1,int tot1)
 11     {
 12         l = l1,r = r1,c = c1,tot = tot1;
 13     }
 14 }tree[4*maxn];
 15 int ans;
 16 
 17 void Init(int p)
 18 {
 19     if(tree[p].l == tree[p].r) return ;
 20     int mid = (tree[p].l + tree[p].r) / 2;
 21     tree[2*p].Node(tree[p].l,mid,2,1);
 22     tree[2*p+1].Node(mid+1,tree[p].r,2,1);
 23     Init(2*p);
 24     Init(2*p+1);
 25 }
 26 void paint(int p,int l,int r,int c)
 27 {
 28     if(tree[p].l == l && tree[p].r == r)
 29     {
 30         tree[p].c = 1 << (c-1);
 31         tree[p].tot = 1;
 32         return ;
 33     }
 34     int mid = (tree[p].l + tree[p].r) / 2;
 35     int T;
 36     if(tree[p].tot == 1)   //如果这个节点只有一种颜色，需要先往下推 
 37     {
 38         T = 0;
 39         for(int i = 0;i < 30;++i)
 40         if(tree[p].c & (1 << i))
 41         {
 42             T = i+1;
 43             break;
 44         }
 45         paint(2*p,tree[p].l,mid,T);
 46         paint(2*p+1,mid+1,tree[p].r,T);
 47     }
 48     if(r <= mid)
 49     {
 50         paint(2*p,l,r,c);
 51     }
 52     if(l <= mid && r > mid)
 53     {
 54         paint(2*p,l,mid,c);
 55         paint(2*p+1,mid+1,r,c);
 56     }
 57     else if(l > mid)
 58     {
 59         paint(2*p+1,l,r,c);
 60     }
 61     tree[p].c = tree[2*p].c | tree[2*p+1].c;   //回溯 
 62     int tt = 0;
 63     for(int i = 0;i < 30;++i)
 64     if(tree[p].c & (1 << i))
 65     tt++;
 66     tree[p].tot = tt;
 67 }
 68 void query(int p,int l,int r)
 69 {
 70     if((tree[p].l == l && tree[p].r == r) || tree[p].tot == 1)
 71     {
 72         ans |= tree[p].c;
 73         return ;
 74     }
 75     int mid = (tree[p].l + tree[p].r) / 2;
 76     if(r <= mid) query(2*p,l,r);
 77     else if(l <= mid && r > mid)
 78     {
 79         query(2*p,l,mid);
 80         query(2*p+1,mid+1,r);
 81     }
 82     else if(l > mid) query(2*p+1,l,r);
 83 }
 84 int main()
 85 {
 86 //    freopen("in.txt","r",stdin);
 87 //    freopen("out.txt","w",stdout);
 88     int n,m;
 89     while(scanf("%d%d",&n,&m),n+m)
 90     {
 91         tree[1].Node(1,n,2,1);
 92         Init(1);    
 93         int a,b,c;
 94         char oper[5];
 95         while(m--)
 96         {
 97             scanf("%s%d%d",oper,&a,&b);
 98             if(oper[0] == ‘P‘)
 99             {
100                 scanf("%d",&c);
101                 paint(1,a,b,c);
102             }
103             else
104             {
105                 ans = 0;
106                 query(1,a,b);
107                 int flag = 1;
108                 for(int i = 0;i < 30;++i)
109                 if(ans & (1 << i))
110                 {
111                     printf(flag? "%d":" %d",i+1); 
112                     flag = 0;
113                 }
114                 puts("");
115             }
116         //    for(int i = 1;i <= 9;++i)
117         //    printf(i == 9? "%d\n":"%d ",tree[i].c);
118         //    for(int i = 1;i <= 9;++i)
119         //    printf(i == 9? "%d\n":"%d ",tree[i].tot);
120         }
121     }
122 }