区间最大公约数

AcWing-246-区间最大公约数

分析

见《进阶指南》第215页。

实现

#include <iostream>
#define ls rt << 1
#define rs rt << 1 | 1
using namespace std;

typedef long long LL;
const int N = 500010;
struct node {
    int l, r;
    LL data;
    #define l(x) t[x].l
    #define r(x) t[x].r
    #define data(x) t[x].data
};
int n, m;
LL a[N], d[N];
node t[N << 2];
LL c[N];

LL gcd (LL a, LL b) {
    return b == 0 ? a : gcd(b, a % b);
}
void update (int rt) {
    data(rt) = gcd(data(ls), data(rs));
}
void build (int rt, int l, int r) {
    l(rt) = l, r(rt) = r;
    if (l == r) {
        data(rt) = d[l];
        return;
    }
    int mid = l + r >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    update(rt);
}
void modify (int rt, int idx, LL val) {
    if (l(rt) == r(rt)) {
        data(rt) += val;
        return;
    }
    int mid = l(rt) + r(rt) >> 1;
    modify(idx <= mid ? ls : rs, idx, val);
    update(rt);
}
LL query (int rt, int l, int r) {
    if (l <= l(rt) && r(rt) <= r) return data(rt);
    int mid = l(rt) + r(rt) >> 1;
    LL res = 0;
    if (l <= mid) res = gcd(res, query(ls, l, r));
    if (r >= mid + 1) res = gcd(res, query(rs, l, r));
    return abs(res);
}
int lowbit (int x) {
    return x & -x;
}
void add (int idx, LL val) {
    while (idx <= n) {
        c[idx] += val;
        idx += lowbit(idx);
    }
}
LL sum (int idx) {
    LL res = 0;
    while (idx >= 1) {
        res += c[idx];
        idx -= lowbit(idx);
    }
    return res;
}

int main () {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++ i) scanf("%lld", &a[i]);

    for (int i = 1; i <= n; ++ i) d[i] = a[i] - a[i - 1];
    build(1, 1, n);
    while (m --) {
        char opt[5];
        scanf("%s", opt);
        if (opt[0] == 'C') {
            int l, r;
            LL val;
            scanf("%d%d%lld", &l, &r, &val);

            modify(1, l, val);
            add(l, val);
            if (r + 1 <= n) {
                modify(1, r + 1, -val);
                add(r + 1, -val);
            }
        } else {
            int l, r;
            scanf("%d%d", &l, &r);
            printf("%lld\n", gcd(a[l] + sum(l), query(1, min(l + 1, r), r)));
        }
    }
    return 0;
}