題目鏈接

題意 ： 給你n個初值，然后進行兩種操作，第一種操作是將（L，R）這一區間上所有的數變成x，第二種操作是將（L，R）這一區間上所有大于x的數a[i]變成gcd（x，a[i]）。輸出最后n個數。

思路 ： 暴力線段樹，將區間進行更新，可以用延遲標記，也可以不用。p數組代表當前節點這一段上的值是不是相同，不全相同就是-1.

1 //4902 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 #include <algorithm> 6 7 using namespace std ; 8 9 #define LL long long 10 LL a ,lz[100011*4],p[100011*4]; 11 12 void pushup(int rt) 13 { 14 if(p[rt << 1] == p[rt << 1 | 1]) 15 p[rt] = p[rt << 1] ; 16 else p[rt] = -1 ; 17 } 18 19 void pushdown(int rt) 20 { 21 if(lz[rt] != -1) 22 { 23 lz[rt << 1] = lz[rt << 1 | 1] = lz[rt] ; 24 p[rt << 1] = p[rt << 1 | 1] = lz[rt] ; 25 lz[rt] = -1 ; 26 } 27 } 28 void build(int l,int r,int rt) 29 { 30 lz[rt] = -1 ; 31 if(l == r) 32 { 33 scanf("%I64d",&a) ; 34 p[rt] = a; 35 return ; 36 } 37 int mid = (l + r) >> 1 ; 38 build(l,mid,rt << 1) ; 39 build(mid+1,r,rt << 1 | 1) ; 40 pushup(rt) ; 41 } 42 43 void update(int L,int R,int l,int r,int rt,LL sc,int flag) 44 { 45 if(flag > 0) 46 { 47 if(l >= L && r <= R) 48 { 49 p[rt] = lz[rt] = sc ; 50 return ; 51 } 52 } 53 else 54 { 55 if(p[rt] != -1 && (l >= L && r <= R)) 56 { 57 if(p[rt] > sc) 58 { 59 lz[rt] = p[rt] = __gcd(p[rt],sc) ; 60 } 61 return ; 62 } 63 } 64 pushdown(rt) ; 65 int mid = (l+r) >> 1 ; 66 if(mid >= L) 67 update(L,R,l,mid,rt << 1,sc,flag) ; 68 if(R > mid) 69 update(L,R,mid+1,r,rt << 1 | 1,sc,flag) ; 70 pushup(rt) ; 71 } 72 73 void output(int l ,int r,int rt) 74 { 75 if(l == r) 76 { 77 printf("%I64d ",p[rt]) ; 78 return ; 79 } 80 pushdown(rt) ; 81 int mid = (l + r) >> 1 ; 82 output(l,mid,rt << 1) ; 83 output(mid+1,r,rt << 1 | 1) ; 84 } 85 int main() 86 { 87 int T ,n,Q ; 88 cin >> T ; 89 while(T--) 90 { 91 scanf("%d",&n) ; 92 build(1,n,1) ; 93 scanf("%d",&Q) ; 94 int t,l,r; 95 LL x ; 96 while(Q--) 97 { 98 scanf("%d %d %d %I64d",&t,&l,&r,&x) ; 99 if(t == 1) 100 update(l,r,1,n,1,x,1) ; 101 else 102 update(l,r,1,n,1,x,-1) ; 103 } 104 output(1,n,1) ; 105 puts("") ; 106 } 107 return 0 ; 108 } View Code

?

轉載于:https://www.cnblogs.com/luyingfeng/p/3885400.html

總結

以上是生活随笔為你收集整理的2014多校第四场1006 || HDU 4902 Nice boat （线段树 区间更新）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。