【每日一题】小阳的贝壳 题解

Description

链接：https://ac.nowcoder.com/acm/problem/26255
来源：牛客网

小阳手中一共有 n 个贝壳，每个贝壳都有颜色，且初始第 i 个贝壳的颜色为 。现在小阳有 3 种操作：

1 l r x：给 [l,r]区间里所有贝壳的颜色值加上 x 。

2 l r：询问 [l,r]区间里所有相邻贝壳颜色值的差（取绝对值） 的最大值（若 l = r 输出 0）。

3 l r ：询问 [l,r]区间里所有贝壳颜色值的最大公约数。

Solution

前置知识:差分数组、线段树

差分数组

设原数组为 , 令 , 称 为 的差分数组。
差分数组有什么好处呢?
首先不难得到
另外，对原数组 进行区间加 的操作时只需要令:

，。这样做的目的是为了让我们每次查询 的时候都能保证 的结果都是比原来多 的，从而实现了区间加法操作。

线段树

线段树是一种能够支持 复杂度进行区间查询，区间修改的数据结构。

题目是经典区间修改及查询问题，需要特定的数据结构进行求解。仔细观察每一个操作，不难发现:

• 操作1能够用上述差分数组的区间加操作完成，转换成线段树的单点修改。
• 操作2查询的差分数组区间的最大绝对值，转换为线段树的区间最大值查询，需要维护一个绝对值最大的值。
• 操作3中，因为 值可以通过线段树维护，由定理 得到启发，我们在查询的时候可以转化为 , 是差分数组 在区间的。

于是通过对差分数组建立线段树，维护线段树上的 三个值，就能解决这道题。
注意线段树上查询区间 时间复杂度是 , 本题保证 , 可视为常数
总体时间复杂度

Code

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
struct node {
  int l, r, maxz, sum, gcd;
}t[N << 2];
int a[N], b[N];
void push_up(int rt) {
  t[rt].maxz = max(t[rt << 1].maxz, t[rt << 1 | 1].maxz);
  t[rt].sum = t[rt << 1].sum + t[rt << 1 | 1].sum;
  t[rt].gcd = __gcd(t[rt << 1].gcd, t[rt << 1 | 1].gcd);
}
void build(int rt, int l, int r) {
  t[rt].l = l, t[rt].r = r;
  if(l == r) {
    t[rt].maxz = abs(b[l]);
    t[rt].gcd = t[rt].sum = b[l];
    return ;
  }
  int mid = t[rt].l + t[rt].r >> 1;
  build(rt << 1, l, mid);
  build(rt << 1 | 1, mid + 1, r);
  push_up(rt);
}
void update(int rt, int x, int val) {
  if(t[rt].l == t[rt].r) {
    t[rt].sum += val;
    t[rt].gcd = t[rt].sum;
    t[rt].maxz = abs(t[rt].sum);
    return ;
  }
  int mid = t[rt].l + t[rt].r >> 1; 
  if(x <= mid) {
    update(rt << 1, x, val);
  } else {
    update(rt << 1 | 1, x, val);
  }
  push_up(rt);
}
int query_max(int rt, int ql, int qr) {
  if(ql <= t[rt].l && qr >= t[rt].r) {
    return t[rt].maxz;
  }
  int mid = t[rt].l + t[rt].r >> 1;
  if(qr <= mid) {
    return abs(query_max(rt << 1, ql, qr));
  } else if(ql > mid) {
    return abs(query_max(rt << 1 | 1, ql, qr));
  } else {
    return abs(max(query_max(rt << 1, ql, mid), query_max(rt << 1 | 1, mid + 1, qr)));
  }
}
int query_sum(int rt, int ql, int qr) {
  if(ql <= t[rt].l && qr >= t[rt].r) {
    return t[rt].sum;
  }
  int mid = t[rt].l + t[rt].r >> 1;
  if(qr <= mid) {
    return query_sum(rt << 1, ql, qr);
  } else if(ql > mid) {
    return query_sum(rt << 1 | 1, ql, qr);
  } else {
    return query_sum(rt << 1, ql, mid) + query_sum(rt << 1 | 1, mid + 1, qr);
  }
}
int query_gcd(int rt, int ql, int qr) {
  if(ql <= t[rt].l && qr >= t[rt].r) {
    return t[rt].gcd;
  }
  int ans = 0;
  int mid = t[rt].l + t[rt].r >> 1;
  //if(ql <= mid) ans = __gcd(ans, query_gcd(rt << 1, ql, qr));
  //if(qr > mid) ans = __gcd(ans, query_gcd(rt << 1 | 1, ql, qr));
  //return ans;
  if(qr <= mid) {
    return query_gcd(rt << 1, ql, qr);
  } else if(ql > mid) {
    return query_gcd(rt << 1 | 1, ql, qr);
  } else {
    return __gcd(query_gcd(rt << 1, ql, mid), query_gcd(rt << 1 | 1, mid + 1, qr)); 
  }
}
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  int n, m; cin >> n >> m;
  for(int i = 1; i <= n; i++) {
    cin >> a[i];
    b[i] = a[i] - a[i - 1];
  }
  build(1, 1, n);
  while(m--) {
    int op, l, r, x; cin >> op;
    if(op == 1) {
      cin >> l >> r >> x;
      update(1, l, x);
      if(r < n) {
        update(1, r + 1, -x);
      }
    } else if(op == 2) {
      cin >> l >> r;
      if(l == r) {
        cout << 0 << '\n';
      } else {
        cout << query_max(1, l + 1, r) << '\n';
      }
    } else {
      cin >> l >> r;
      if(l == r) {
        cout << query_sum(1, 1, l) << '\n';
      } else {
        cout << abs(__gcd(query_sum(1, 1, l), query_gcd(1, l + 1, r))) << '\n';
      }
    }
  }
  return 0;
}