[线段树 + 数论 + 树状数组]求区间最大公约数 Interval GCD

区间最大公约数

原题链接：区间最大公约数

题目大意

和线段树的操作差不多，给你一个l, r让你都加d， 或者询问你l, r的最大公约数

题目题解

没学过初等数论吃大亏，写了一早上，以后abs一定要加std::

根据更相减损之术我们知道，\(gcd(x, y) = gcd(x, y - x)\) 那么可以拓展出三个数的情况 \(gcd(x,y,z) = gcd(x, y-x, z-y)\) 这是成立的

因为我们可以构造一个长度为\(n\)的新数列b，这个b是a的差分序列。用线段树维护序列b的区间最大公约数，（和上面的结论一样）

这样一来，我们的查询就解决了 直接gcd(a[l], ask(1, l + 1, r)) （想想 为什么？再看看上面的推导公式）

修改的话，很明显在b上是单点修改，在a上也要维护，可以用树状数组维护a值

代码如下

//#define fre yes

#include <cmath>
#include <cstdio>
#include <iostream>
#define int long long

const int N = 500005;
struct Node {
    int l, r;
    long long ans;
} tree[N << 2];
int a[N], b[N], c[N];

long long cnt;

long long gcd(long long x, long long y) {
    return y ? gcd(y, x % y) : x;
}

namespace SegmentTree {
    inline void build(int rt, int l, int r) {
        tree[rt].l = l, tree[rt].r = r;
        if(l == r) {
            tree[rt].ans = b[l];
            return ;
        }

        int mid = (l + r) >> 1;
        build(rt * 2, l, mid);
        build(rt * 2 + 1, mid + 1, r);
        tree[rt].ans = gcd(tree[rt * 2].ans, tree[rt * 2 + 1].ans);
    }

    inline void change_point(int rt, int x, int k) {
        if(tree[rt].l == tree[rt].r) {
            tree[rt].ans += k;
            return ;
        }

        int mid = (tree[rt].l + tree[rt].r) >> 1;
        if(mid >= x) change_point(rt * 2, x, k);
        else change_point(rt * 2 + 1, x, k);
        tree[rt].ans = gcd(tree[rt * 2].ans, tree[rt * 2 + 1].ans);
    }

    inline void ask(int rt, int l, int r) {
        if(tree[rt].l >= l && tree[rt].r <= r) {
            cnt = gcd(cnt, tree[rt].ans);
            return ;
        }

        int mid = (tree[rt].l + tree[rt].r) >> 1;
        if(l <= mid) ask(rt * 2, l, r);
        if(r > mid) ask(rt * 2 + 1, l, r);
    }
}

int n;
namespace BIT {
    int lowbit(int x) {
        return x & (-x);
    }

    inline void add(int x, int k) {
        while(x <= n) {
            c[x] += k;
            x += lowbit(x);
        }
    }

    int ask(int x) {
        long long res = 0;
        while(x) {
            res += c[x];
            x -= lowbit(x);
        } return res;
    }
}

signed main() {
    static int m;
    scanf("%lld %lld", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        b[i] = a[i] - a[i - 1];
    } SegmentTree::build(1, 1, n);

    char c[3];
    for (int i = 1; i <= m; i++) {
        scanf("%s", c + 1);
        if(c[1] == 'C') {
            int l, r, d;
            scanf("%lld %lld %lld", &l, &r, &d);
            SegmentTree::change_point(1, l, d);
            BIT::add(l, d);
            if(r + 1 <= n) {
                SegmentTree::change_point(1, r + 1, -d);
                BIT::add(r + 1, -d);
            }
        } else {
            cnt = 0; int l, r;
            scanf("%lld %lld", &l, &r);
            SegmentTree::ask(1, l + 1, r);
            printf("%lld\n", gcd(a[l] + BIT::ask(l), std::abs(cnt)));
        }
    } return 0;
}