「CH 4302」Interval GCD (树状数组 + 线段树 + GCD更相减损术 + 差分序列)

CH 4302
题意：给出一个$n$长序列，你要支持区间增加和查询区间$gcd$。

显然的线段树，但是区间增加对于$gcd$不好更新$lazy$标记。那么我们只能考虑一下能不能只单点修改，那么我们就想到了差分序列。
根据$gcd(a,b)=gcd(a, b-a)$推出$gcd(a,b,c)=gcd(a,b-a,c-b)$然后推广到更多数字可以发现，区间$gcd$值就等于区间第一个数和之后区间的差分序列的$gcd$相等。
所以只需要维护差分序列的$gcd$，线段树变为了单点修改区间查$gcd$。

因为要用到原数组，所以开一个 BIT 维护原数组的差分序列即可

知识点：
1、pushup不要在叶节点进行。
2、$gcd$一般为正数。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<set>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const LL MAXN = 500000 + 5;

    LL n, m, qwq[MAXN], bqwq[MAXN];
    LL a[MAXN];

    LL gcd(LL a, LL b) {return b == 0 ? a : gcd(b, a % b);}
    LL abss(LL x) {return x > 0 ? x : -x;}
    LL lowbit(LL x) {return x & (-x);}
    void add(LL x, LL p) {
        for (LL i = x; i <= n; i += lowbit(i)) a[i] += p;
    }
    LL query(LL x) {
        LL ret = 0;
        for (LL i = x; i; i -= lowbit(i)) ret += a[i];
        return ret;
    }

    #define lc (o << 1)
    #define rc (o << 1 | 1)
    #define M ((l + r) >> 1)
    LL gcdv[MAXN * 4];
    void pushup(LL o) {
        gcdv[o] = gcd(gcdv[lc], gcdv[rc]);
    }
    void build(LL o, LL l, LL r) {
        if (l == r) gcdv[o] = bqwq[l]; else {
            build(lc, l, M), build(rc, M + 1, r);
            pushup(o);
        }
    }
    void update(LL o, LL l, LL r, LL p, LL v) {
        if (l == r) {gcdv[o] += v; return ;} // 不要加错了
        if (p <= M) update(lc, l, M, p, v); 
        else update(rc, M + 1, r, p, v); 
        pushup(o);
    }
    LL queryGCD(LL o, LL l, LL r, LL x, LL y) {
        if (x <= l && r <= y) {
            return gcdv[o];
        }
        LL ret = 0ll;
        if (x <= M) ret = gcd(ret, queryGCD(lc, l, M, x, y));
        if (M < y) ret = gcd(ret, queryGCD(rc, M + 1, r, x, y));
        return ret;
    }

    void clean() {
        ms(a, 0), ms(bqwq, 0);
    }
    int solve() {
        clean();
        scanf("%lld%lld", &n, &m);
        for (LL i = 1; i <= n; ++i) scanf("%lld", &qwq[i]); qwq[0] = 0;
        for (LL i = 1; i <= n; ++i) bqwq[i] = qwq[i] - qwq[i - 1];
        for (LL i = 1; i <= n; ++i) add(i, bqwq[i]);
        build(1, 1, n + 1);
        while (m--) {
            char s[4]; scanf("%s", s);
            if (s[0] == 'Q') {
                LL x, y; scanf("%lld%lld", &x, &y);
                printf("%lld\n", abss(gcd(queryGCD(1, 1, n + 1, x + 1, y), query(x)))); // 注意 abss
            } else {
                LL x, y, d; scanf("%lld%lld%lld", &x, &y, &d);
                add(x, d), add(y + 1, -d);
                update(1, 1, n + 1, x, d), update(1, 1, n + 1, y + 1, -d);
            }
        }
        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}