小阳的贝壳_牛客博客

小阳的贝壳

这里最难维护的应该是区间 $gcd$ 了，但是我们有一个结论 $gcd(a_1, a_2, \dots a_{n}) = gcd(a_1, a_2 - a_1, \dots a_n - a_{n - 1})$ ，所以这一步可以转换为维护整个序列的差分。

对于操作一：我们只要对 $l$ 端点的值增加 $x$ ，对 $r + 1$ 端点的值减小 $x$ 。

对于操作二：我们只要得到差分数组里的绝对值最大值就行了。

对于操作三：我们首先要得到 $a_l$ ，然后得到 $gcd(a_{l + 1} - a_l, a_{l + 2} - a_{l + 1}, \dots a_r - a_{r - 1})$ 这一段差分序列的 $gcd$ ，然后再于 $a_l$ 求一个 $gcd$ 即为答案。

对一整颗线段树我们只要维护三个值：区间 $gcd$ 、区间绝对值最大、区间和，我们就可以完成上面的三个操作了。

然后对某些线段树上的操作特判防止数组越界即可。

#include <bits/stdc++.h>
#define mid (l + r >> 1)
#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r
#define ls rt << 1
#define rs rt << 1 | 1

using namespace std;

typedef long long ll;

const int N = 1e5 + 10;

ll maxn[N << 2], gd[N << 2], sum[N << 2], a[N];

void push_up(int rt) {
  sum[rt] = sum[ls] + sum[rs];
  gd[rt] = __gcd(gd[ls], gd[rs]);
  maxn[rt] = max(maxn[ls], maxn[rs]);
}

void build(int rt, int l, int r) {
  if (l == r) {
    gd[rt] = abs(a[l]);
    maxn[rt] = abs(a[l]);
    sum[rt] = a[l];
    return ;
  }
  build(lson);
  build(rson);
  push_up(rt);
}

void update(int rt, int l, int r, int L, int R, int x) {
  if (l >= L && r <= R) {
    sum[rt] += x;
    gd[rt] = abs(sum[rt]);
    maxn[rt] = abs(sum[rt]);
    return ;
  }
  if (L <= mid) update(lson, L, R, x);
  if (R > mid)  update(rson, L, R, x);
  push_up(rt);
}

ll query_max(int rt, int l, int r, int L, int R) {
  if (l >= L && r <= R) {
    return maxn[rt];
  }
  ll ans = 0;
  if (L <= mid) ans = max(ans, query_max(lson, L, R));
  if (R > mid)  ans = max(ans, query_max(rson, L, R));
  return ans;
}

ll query_sum(int rt, int l, int r, int L, int R) {
  if (l >= L && r <= R) {
    return sum[rt];
  }
  ll ans = 0;
  if (L <= mid) ans += query_sum(lson, L, R);
  if (R > mid)  ans += query_sum(rson, L, R);
  return ans;
}

ll query_gcd(int rt, int l, int r, int L, int R) {
  if (l >= L && r <= R) {
    return gd[rt];
  }
  ll ans = 0;
  if (L <= mid) ans = __gcd(ans, query_gcd(lson, L, R));
  if (R > mid)  ans = __gcd(ans, query_gcd(rson, L, R));
  return ans;
}

int main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = n; i >= 1; i--) {
    a[i] -= a[i - 1];
  }
  build(1, 1, n);
  for (int i = 1; i <= m; i++) {
    int op, l, r, x;
    cin >> op >> l >> r;
    if (op == 1) {
      cin >> x;
      update(1, 1, n, l, l, x);
      if (r + 1 <= n) {
        update(1, 1, n, r + 1, r + 1, -x);
      }
    }
    else if (op == 2) {
      if (l == r) {
        cout << "0\n";
      }
      else {
        cout << query_max(1, 1, n, l + 1, r) << "\n";
      }
    }
    else {
      if (l == r) {
        cout << query_sum(1, 1, n, 1, r) << "\n";
      }
      else {
        ll cur = query_sum(1, 1, n, 1, l);
        cout << __gcd(cur, query_gcd(1, 1, n, l + 1, r)) << "\n";
      }
    }
  }
  return 0;
}