(线段树)AcWing 246. 区间最大公约数

对于一个数组
$gcd(a_1,a_2,...,a_n) == gcd(a_1, a_2-a_1,...,a_n-a_{n-1})$
也就是一个数组的最大公约数等于这个数组的差分数组的gcd

我们要查的是 $gcd(a_l, a_{l+1},...,a_{r})$
也就是 $gcd(a_l, a_{l+1}-a_l,...,a_{r}-a_{r-1})$

因为已经是差分数组了，因此求 $a_l$ 需要求前缀和（这里穿插在线段树中，用Node节点里的sum表示）
然后再和 $gcd(a_{l+1}-a_l,...,a_{r}-a_{r-1})$ 做gcd，即为答案

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 500010;
int n, m;
LL w[N];

struct Node {
    int l, r;
    LL sum, g;
} tr[4 * N];

LL gcd(LL a, LL b) {
    return b ? gcd(b, a % b) : a;
}

void pushup(Node &u, Node &l, Node &r) {
    u.sum = l.sum + r.sum;
    u.g = gcd(l.g, r.g);
}

void pushup(int u) {
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void build(int u, int l, int r) {
    if (l == r)tr[u] = {l, l, w[l], w[l]};
    else {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int x, LL v) {
    if (tr[u].l == x && tr[u].r == x) {
        tr[u].sum += v;
        tr[u].g += v;
    } else {
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid)modify(u << 1, x, v);
        else modify(u << 1 | 1, x, v);
        pushup(u);
    }
}

Node query(int u, int l, int r) {
    if (l <= tr[u].l && tr[u].r <= r)return tr[u];
    else {
        int mid = tr[u].l + tr[u].r >> 1;
        if (r <= mid) return query(u << 1, l, r);
        else if (l > mid)return query(u << 1 | 1, l, r);
        else {
            Node left = query(u << 1, l, r);
            Node right = query(u << 1 | 1, l, r);
            Node res;
            pushup(res, left, right);
            return res;
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)cin >> w[i];
    for (int i = n; i > 0; i--)w[i] -= w[i - 1];

    build(1, 1, n);

    while (m--) {
        string op;
        LL l, r, d;
        cin >> op >> l >> r;
        if (op[0] == 'Q') {
            Node res1 = query(1, 1, l);
            Node res2({0, 0, 0, 0});
            if (l + 1 <= r) res2 = query(1, l + 1, r);
            LL a = res1.sum, b = res2.g;
            cout << abs(gcd(a, b)) << endl;
        } else {
            cin >> d;
            modify(1, l, d);
            if (r + 1 <= n) modify(1, r + 1, -d);
        }
    }

    return 0;
}

最后编辑于：2021.03.31 18:25:43