首页 > 代码库 > HDU 5023 A Corrupt Mayor's Performance Art(线段树区间更新)
HDU 5023 A Corrupt Mayor's Performance Art(线段树区间更新)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5023
解题报告:一面墙长度为n,有N个单元,每个单元编号从1到n,墙的初始的颜色是2,一共有30种颜色,有两种操作:
P a b c 把区间a到b涂成c颜色
Q a b 查询区间a到b的颜色
线段树区间更新,每个节点保存的信息有,存储颜色的c,30种颜色可以压缩到一个int型里面存储,然后还有一个tot,表示这个区间一共有多少种颜色。
对于P操作,依次往下寻找,找要更新的区间,找到要更新的区间之前,如果当前所在的区间的总共的颜色只有一种,那么就要把这个区间的信息压到这个节点的两个子节点中,
然后再选择要更新的那个区间所在的那个区间继续往下更新。
对于Q操作,这个可以随便了,反正区间的信息都存在了每个节点的C 里面,只要按规则取出来就行了。
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 else104 {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 }
HDU 5023 A Corrupt Mayor's Performance Art(线段树区间更新)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。