首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。