首页 > 代码库 > HDU 4902 Nice boat 2014杭电多校训练赛第四场F题（线段树区间更新）
HDU 4902 Nice boat 2014杭电多校训练赛第四场F题（线段树区间更新）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4902
解题报告：输入一个序列，然后有q次操作，操作有两种，第一种是把区间 (l,r) 变成x，第二种是把区间 (l,r) 中大于x的数跟 x 做gcd操作。
线段树区间更新的题目，每个节点保存一个最大和最小值，当该节点的最大值和最小值相等的时候表示这个区间所有的数字都是相同的，可以直接对这个区间进行1或2操作，
进行1操作时，当还没有到达要操作的区间但已经出现了节点的最大值跟最小值相等的情况时，说明这个区间的值都是相同的，但现在我只要在这个区间的一部分进行1操作，所以
我要先把这个节点的最大的最小值往下压，直到找到了要操作的区间。
进行2操作时，如果该区间的最大值都小于x，则可以直接退出，如果最大值大于x，则表示这个区间可以进行gcd操作，然后继续往下，直到找到最大值跟最小值相等的区间才开始
进行gcd操作，进行gcd操作之后不要忘了更新父节点的最大最小值。
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 using namespace std; 6 #define maxn 100005 7 struct node 8 { 9 int Max,Min,l,r; 10 }tree[4*maxn]; 11 void build(int p) 12 { 13 if(tree[p].l == tree[p].r) return ; 14 int mid = (tree[p].l + tree[p].r) / 2; 15 tree[2*p].Max = tree[2*p+1].Max = -1; 16 tree[2*p].Min = tree[2*p+1].Min = 0x7fffffff; 17 tree[2*p].l = tree[p].l; 18 tree[2*p].r = mid; 19 tree[2*p+1].l = mid + 1; 20 tree[2*p+1].r = tree[p].r; 21 build(2*p); 22 build(2*p+1); 23 } 24 void push(int p,int l,int d) 25 { 26 tree[p].Max = max(tree[p].Max,d); 27 tree[p].Min = min(tree[p].Min,d); 28 if(tree[p].l == tree[p].r) return ; 29 int mid = (tree[p].l + tree[p].r) / 2; 30 if(l <= mid) push(2*p,l,d); 31 else push(2*p+1,l,d); 32 } 33 int gcd(int a,int b) 34 { 35 return b == 0? a : gcd(b,a%b); 36 } 37 void oper1(int p,int l,int r,int x) 38 { 39 if(tree[p].l == l && tree[p].r == r) 40 { 41 tree[p].Max = tree[p].Min = x; 42 return ; 43 } 44 int mid = (tree[p].l + tree[p].r) / 2; 45 if(tree[p].Max == tree[p].Min) 46 { 47 oper1(2*p+1,mid+1,tree[p].r,tree[p].Max); //先把当前区间的值往下压 48 oper1(2*p,tree[p].l,mid,tree[p].Max); 49 } 50 tree[p].Max = max(tree[p].Max,x); 51 tree[p].Min = min(tree[p].Min,x); 52 if(r <= mid) 53 oper1(2*p,l,r,x); 54 else if(l <= mid && r > mid) 55 { 56 oper1(2*p,l,mid,x); 57 oper1(2*p+1,mid+1,r,x); 58 } 59 else oper1(2*p+1,l,r,x); 60 } 61 void oper2(int p,int l,int r,int x) 62 { 63 int mid = (tree[p].l + tree[p].r) / 2; 64 if(tree[p].l == l && tree[p].r == r) 65 { 66 if(tree[p].Max < x) return ; //最大的都不可以进行gcd操作，直接退出 67 if(tree[p].Max == tree[p].Min) //找到了值都相同的区间，可以直接进行gcd操作 68 { 69 if(tree[p].Max > x) tree[p].Max = tree[p].Min = gcd(tree[p].Max,x); 70 return ; 71 } 72 else if(tree[p].Max > x) 73 { 74 oper2(2*p,l,mid,x); 75 oper2(2*p+1,mid+1,r,x); 76 } 77 return ; 78 } 79 if(tree[p].Max == tree[p].Min) //还没找到操作的区间之前碰到了这个，则也要通过1操作，把这个节点的值往下压 80 { 81 oper1(2*p,tree[p].l,mid,tree[p].Max); 82 oper1(2*p+1,mid+1,tree[p].r,tree[p].Max); 83 } 84 if(r <= mid) 85 oper2(2*p,l,r,x); 86 else if(l <= mid && r > mid) 87 { 88 oper2(2*p,l,mid,x); 89 oper2(2*p+1,mid+1,r,x); 90 } 91 else oper2(2*p+1,l,r,x); 92 if(tree[p].l != tree[p].r) //记得更新父节点的最大最小值 93 { 94 tree[p].Max = max(tree[2*p].Max,tree[2*p+1].Max); 95 tree[p].Min = min(tree[2*p].Min,tree[2*p+1].Min); 96 } 97 } 98 int query(int p,int l) 99 {100 int mid = (tree[p].l + tree[p].r) / 2;101 if(tree[p].Max == tree[p].Min)102 return tree[p].Max;103 if(l <= mid) return query(2*p,l);104 else return query(2*p+1,l);105 }106 107 int main()108 {109 int T,n;110 scanf("%d",&T);111 while(T--)112 {113 scanf("%d",&n);114 tree[1].Max = -1;115 tree[1].Min = 0x7fffffff;116 tree[1].l = 1;117 tree[1].r = n;118 build(1);119 int d;120 for(int i = 1;i <= n;++i)121 {122 scanf("%d",&d);123 push(1,i,d);124 }125 int q,t,l,r,x;126 scanf("%d",&q);127 while(q--)128 {129 scanf("%d%d%d%d",&t,&l,&r,&x);130 if(t == 1) oper1(1,l,r,x);131 else oper2(1,l,r,x);132 }133 for(int i = 1;i <= n;++i) //输出有点不同，PE了好几次，最后也是有空格的 134 printf("%d ",query(1,i));135 puts("");136 }137 return 0;138 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。