题解：P10463 Interval GCD

forever_nope · 2024-07-12 19:45:54 · 题解

注意到，我们的线段树在维护 \gcd 的时候，

• 容易完成单点修改，而区间修改难以完成。

于是，我们考虑将区间修改，替换为单点修改。

那么这就是差分，我们把原数组替换为其差分数组。

然而，我们需要区间 \gcd，下面是性质：

• 序列的 \gcd 等于其差分序列的 \gcd 这一性质。

考虑证明，

考虑 n=2

此时，序列为，

我们根据更相减损术，

注意到这个就是差分的形式。

考虑 n=3

此时，序列为，

我们列出式子，根据 \gcd 的性质，

注意到这个就是差分的形式。

考虑任意 n

此时，序列为，

我们列出，

这个可以类比上一个得出。

具体实现

注意要维护前缀和，因为差分是以某个序列（而不是全局）中第一个元素为基准的。

注意如果 l=r 需要特判。

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"
#define gcd(x, y) __gcd(abs(x), abs(y))

constexpr int N = 5e5 + 10;

#define int ll
using ll = long long;

int n, m, ori[N];

// ----------------------------------------------------------------------------

#define ls(k) ((k) << 1)
#define rs(k) ((k) << 1 | 1)

struct node {
    int l, r;
    int sum, v;
} a[N << 2];

void push_up(int k) {
    a[k].sum = a[ls(k)].sum + a[rs(k)].sum;
    a[k].v = gcd(a[ls(k)].v, a[rs(k)].v);
}

void action(int k, int v) {
    a[k].sum += v, a[k].v += v;
}

void build(int k, int l, int r) {
    a[k].l = l, a[k].r = r;
    if (l == r) return action(k, ori[l] - ori[l - 1]);
    int mid = l + r >> 1;
    build(ls(k), l, mid), build(rs(k), mid + 1, r);
    push_up(k);
}

void add(int k, int x, int v) {
    int l = a[k].l, r = a[k].r;
    if (l == r) return action(k, v);
    int mid = l + r >> 1;
    // [l, mid] [mid + 1, r]
    if (x <= mid) add(ls(k), x, v);
    else add(rs(k), x, v);
    push_up(k);
}

pair<int, int> query(int k, int p, int q) {
    int l = a[k].l, r = a[k].r;
    if (l >= p && r <= q) return make_pair(a[k].sum, a[k].v);
    int mid = l + r >> 1;
    // [l, mid] [mid + 1, r]
    if (q <= mid) return query(ls(k), p, q);
    if (p >= mid + 1) return query(rs(k), p, q);
    auto z = query(ls(k), p, q), y = query(rs(k), p, q);
    return make_pair(z.first + y.first, gcd(z.second, y.second));
}

// ----------------------------------------------------------------------------

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cin >> n >> m;
    copy_n(istream_iterator<int>(cin), n, ori + 1);
    build(1, 1, n);
    while (m--) {
        string op;
        int l, r, d;
        cin >> op >> l >> r;
        if (op == "Q") {
            if (l == r) cout << query(1, 1, r).first << endl;
            else {
                int st = query(1, 1, l).first;
                int ed = query(1, l + 1, r).second;
                cout << gcd(st, ed) << endl;
            }
        }
        else {
            cin >> d;
            add(1, l, d);
            if (r != n) add(1, r + 1, -d);
        }
    }
    return 0;
}