hdu 4902 Nice boat 线段树

给n个数，两种操作，第一种是将区间内的数变成x，第二种是将区间内大于x的数变为gcd（x, a[i])。

开三个数组，一个记录区间最大值，这样可以判断是否更新这一区间，一个lazy标记，还有一个num数组记录这一区间的数是否相同，如果不同则为-1。然后暴力更新就可以

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 #define pb(x) push_back(x)
  4 #define ll long long
  5 #define mk(x, y) make_pair(x, y)
  6 #define lson l, m, rt<<1
  7 #define mem(a) memset(a, 0, sizeof(a))
  8 #define rson m+1, r, rt<<1|1
  9 #define mem1(a) memset(a, -1, sizeof(a))
 10 #define mem2(a) memset(a, 0x3f, sizeof(a))
 11 #define rep(i, a, n) for(int i = a; i<n; i++)
 12 #define ull unsigned long long
 13 typedef pair<int, int> pll;
 14 const double PI = acos(-1.0);
 15 const double eps = 1e-8;
 16 const int mod = 1e9+7;
 17 const int inf = 1061109567;
 18 const int dir[][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
 19 const int maxn = 1e5+5;
 20 int maxx[maxn<<2], cnt[maxn<<2], num[maxn<<2];
 21 void pushUp(int rt) {
 22     if(num[rt<<1] == num[rt<<1|1])
 23         num[rt] = num[rt<<1];
 24     else
 25         num[rt] = -1;
 26     maxx[rt] = max(maxx[rt<<1], maxx[rt<<1|1]);
 27 }
 28 void pushDown(int rt) {
 29     if(~cnt[rt]) {
 30         cnt[rt<<1] = cnt[rt<<1|1] = cnt[rt];
 31         num[rt<<1] = num[rt<<1|1] = num[rt];
 32         maxx[rt<<1] = maxx[rt<<1|1] = maxx[rt];
 33         cnt[rt] = -1;
 34     }
 35 }
 36 void update(int val, int L, int R, int l, int r, int rt) {
 37     if(L<=l&&R>=r) {
 38         cnt[rt] = maxx[rt] = num[rt] = val;
 39         return ;
 40     }
 41     pushDown(rt);
 42     int m = l+r>>1;
 43     if(L<=m)
 44         update(val, L, R, lson);
 45     if(R>m)
 46         update(val, L, R, rson);
 47     pushUp(rt);
 48 }
 49 void update1(int L, int R, int l, int r, int rt, int val) {
 50     if(L<=l&&R>=r&&num[rt]>val) {
 51         cnt[rt] = maxx[rt] = num[rt] = __gcd(num[rt], val);
 52         return ;
 53     }
 54     pushDown(rt);
 55     int m = l+r>>1;
 56     if(L<=m&&maxx[rt<<1]>val)
 57         update1(L, R, lson, val);
 58     if(R>m&&maxx[rt<<1|1]>val)
 59         update1(L, R, rson, val);
 60     pushUp(rt);
 61 }
 62 void build(int l, int r, int rt) {
 63     if(l == r) {
 64         scanf("%d", &maxx[rt]);
 65         num[rt] = maxx[rt];
 66         return ;
 67     }
 68     int m = l+r>>1;
 69     build(lson);
 70     build(rson);
 71     pushUp(rt);
 72 }
 73 void print(int l, int r, int rt) {
 74     if(l == r) {
 75         printf("%d ", num[rt]);
 76         return ;
 77     }
 78     pushDown(rt);
 79     int m = l+r>>1;
 80     print(lson);
 81     print(rson);
 82 }
 83 int main()
 84 {
 85     int t, n, z, q, x, y, sign;
 86     cin>>t;
 87     while(t--) {
 88         cin>>n;
 89         build(1, n, 1);
 90         cin>>q;
 91         mem1(cnt);
 92         while(q--) {
 93             scanf("%d%d%d%d", &sign, &x, &y, &z);
 94             if(sign == 1) {
 95                 update(z, x, y, 1, n, 1);
 96             } else {
 97                 update1(x, y, 1, n, 1, z);
 98             }
 99         }
100         print(1, n, 1);
101         cout<<endl;
102     }
103 }

hdu 4902 Nice boat 线段树

相关推荐