首页 > 代码库 > 2014 网选 广州赛区 hdu 5023 A Corrupt Mayor's Performance Art

2014 网选 广州赛区 hdu 5023 A Corrupt Mayor's Performance Art

 1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<algorithm> 5 #define N 1000005 6 using namespace std; 7  8 int c[35]; 9 int tree[N*4];//正值表示该节点所管理的区间的颜色是纯色,-1表示的是非纯色10 int n, m; 11 12 void buildT(int ld, int rd, int p){13     if(ld <= rd){14         tree[p] = 2;//初始每一个节点的颜色全部都是215         if(ld == rd) return;16         int mid=(ld + rd)>>1;17         buildT(ld, mid, p<<1);18         buildT(mid+1, rd, p<<1|1);19     }20 }21 22 void updateT(int ld, int rd, int a, int b, int col, int p){23     24     if(ld > rd) return ;25     26     if(tree[p] == col) return ;27     28     if(ld == a && rd == b){29         tree[p] = col;30         return ;31     }32     int mid = (ld + rd)>>1;33     34     if(tree[p] != -1){// p所管的区间之前是纯色,现在不是纯色了,向下更新其孩子节点的颜色为它的颜色35         tree[p<<1] = tree[p<<1 | 1] = tree[p];36         tree[p] = -1;37     }38     39     if(a > mid)40         updateT(mid+1, rd, a, b, col, p<<1 | 1);41     else if(b <= mid)42         updateT(ld, mid, a, b, col, p<<1);43     else{44         updateT(ld, mid, a, mid, col, p<<1);45         updateT(mid+1, rd, mid+1, b, col, p<<1 | 1);46     }47 }48 49 int cnt;50 51 void querryT(int ld, int rd, int a, int b, int p){52     if(ld>rd) return ; 53     54     if(tree[p] != -1){//一直找到纯色的区间!55         c[tree[p]]=1;56         return ;57     }58     59     int mid = (ld+rd)>>1;60     if(a > mid)61         querryT(mid+1, rd, a, b, p<<1 | 1);62     else if(b <= mid)63         querryT(ld, mid, a, b, p<<1) ;64     else{65         querryT(ld, mid, a, mid, p<<1);66         querryT(mid+1, rd, mid+1, b, p<<1 | 1);67     }68 }69 70 int main(){71     while(scanf("%d%d", &n, &m) && (n || m)){72         char ch[2];73         int a, b, k;74         buildT(1, n, 1);75         while(m--){76             scanf("%s", ch);77             if(ch[0] == P){78                 scanf("%d%d%d", &a, &b, &k);79                 updateT(1, n, a, b, k, 1);80             }81             else{82                 scanf("%d%d", &a, &b);83                 memset(c, 0, sizeof(c));84                 querryT(1, n, a, b, 1);85                 int i;86                 for(i=1; i<=30; ++i)87                     if(c[i]){88                          printf("%d", i);89                          break;90                     }91                 for(++i; i<=30; ++i)92                     if(c[i]) printf(" %d", i);93                 printf("\n");94             }95         }96     }97     return 0;98 } 

 

2014 网选 广州赛区 hdu 5023 A Corrupt Mayor's Performance Art