AcWing：246. 区间最大公约数（线段树 + 增量数组(树状数组) + 差分序列）

给定一个长度为N的数列A，以及M条指令，每条指令可能是以下两种之一：

1、“C l r d”，表示把 A[l],A[l+1],…,A[r] 都加上 d。

2、“Q l r”，表示询问 A[l],A[l+1],…,A[r] 的最大公约数(GCD)。

对于每个询问，输出一个整数表示答案。

输入格式

第一行两个整数N,M。

第二行N个整数A[i]。

接下来M行表示M条指令，每条指令的格式如题目描述所示。

输出格式

对于每个询问，输出一个整数表示答案。

每个答案占一行。

数据范围

N≤500000,M≤100000N≤500000,M≤100000

输入样例：

输出样例：

算法：线段树 + 增量数组(树状数组) + 差分序列

题解：

　　性质:

gcd(a, b) = gcd(a, b - a)
gcd(a, b, c) = gcd(a, b - a, c - b)
acd(a₁, a₂, ... , a_n) = gcd(a₁, a₂ - a₁, ... , a_n - a_n-1)

　　利用这条性质来求解此题

对用询问“Q l r”来说，可以求出结果__gcd(arr[l], query(1, l + 1, r)，就是同上面的性质，前面那个arr[l]就是性质里面的第一个数，后面的就是存在了线段树里面差分序列，求出(l + 1, r)区间的最大公约数即可。（其中的arr[l]等于原本数组里面的值加上后面更改的值，更改的值记录再树状数组里面）。
对于询问“C l r d”来说，只需要修改树状数组里面的值，以及线段树里面的值即可。

注意：题目会爆int，需要用long long。

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cmath>

using namespace std;

typedef long long ll;

const int maxn = 5e5+;

struct node {

    ll l, r;

    ll dat;

}tree[maxn << ];   //维护差分序列的线段树

ll n, m;

ll d[maxn];         //差分数组

ll arr[maxn];       //原始数组

ll T[maxn];         //增量数组（树状数组）

ll lowbit(ll x) {

    return x & (-x);

}

void pushup(ll root) {

    tree[root].dat = __gcd(tree[root << ].dat, tree[root <<  | ].dat);

}

void build(ll root, ll l, ll r) {

    tree[root].l = l;

    tree[root].r = r;

    if(l == r) {

        tree[root].dat = d[l];

        return;

    }

    ll mid = (l + r) >> ;

    build(root << , l, mid);

    build(root <<  | , mid + , r);

    pushup(root);

} 

void add(ll x, ll val) {

    while(x <= n) {

        T[x] += val;

        x += lowbit(x);

    }

}

ll ask(ll x) {

    ll res = ;

    while(x > ) {

        res += T[x];

        x -= lowbit(x);

    }

    return res;

}

void update(ll root, ll pos, ll val)  {

    ll l = tree[root].l;

    ll r = tree[root].r;

    if(l == r) {

        tree[root].dat += val;

        return;

    }

    ll mid = (l + r) >> ;

    if(pos <= mid) {

        update(root << , pos, val);

    } else {

        update(root <<  | , pos, val);

    }

    pushup(root);

}

ll query(ll root, ll x, ll y) {

    ll l = tree[root].l;

    ll r = tree[root].r;

    if(x <= l && r <= y) {

        return tree[root].dat;

    }

    ll mid = (l + r) >> ;

    ll res = ;

    if(x <= mid) {

        res = __gcd(res, query(root << , x, y));

    }

    if(y > mid) {

        res = __gcd(res, query(root <<  | , x, y));

    }

    return abs(res);        //注意：这里需要加绝对值，因为可能出现负数

}

int main() {

    scanf("%lld%lld", &n, &m);

    for(ll i = ; i <= n; i++) {

        scanf("%lld", &arr[i]);

        d[i] = arr[i] - arr[i - ];         //构建差分数组

    }

    build(, , n);

    while(m--) {

        char str[];

        ll l, r, val;

        scanf("%s", str);

        if(str[] == 'Q') {

            scanf("%lld %lld", &l, &r);

            ll now = arr[l] + ask(l);   //获取当前位置的值（原始数组 + 增量数组）

            printf("%lld\n", __gcd(now, query(, l + , r)));   //与后面的部分求最大公约数

        } else {

            scanf("%lld %lld %lld", &l, &r, &val);

            add(l, val);

            add(r + , -val);

            update(, l, val);

            if(r < n) {     //判断是否会越界

                update(, r + , -val);

            }

        }

    }

    return ;

}

巴特西