分析

• 本题中存在两个操作

（1）区间[L, R]增加一个数；

（2）求区间内的最大公约数；

• 这是一个区间修改，区间查询的问题，我们要考虑每个节点内部需要存储哪些信息？首先，必须存储区间端点和对应的最大公约数，如下：

struct Node {
    int l, r;
    int d;  // 区间[l, r]之间数据的最大公约数
}

• 现在考虑我们能不能使用上述信息从子节点得到父节点的最大公约数呢？答案是可以的，父节点的最大公约数等于所有子节点最大公约数的最大公约数。因此，如果只有查询的话，维护一个最大公约数就足已；但是，我们还有修改操作，我们需要考虑怎么处理修改的情况。

• 这里可以使用差分的思想，假设我们使用小括号表示数据的最大公约数，即$(a, b)$表示a和b的最大公约数，下面证明：

$$ (a_1, a_2, a_3 …, a_n) == (a1, a_2-a_1, a_3-a_2, …, a_n-a_{n-1}) $$

（1）首先证明左边$\le$右边，假设d是左边的公约数，则d一定是右边的最大公约数；

（2）再证明左边$\ge$右边，假设d是右边的最大公约数，则d能整除$a_1$，因为d能整除$a_2-a_1$，所以d能整除$(a_2-a_1)+a_1=a_2$，以此类推d能整除$a_3,…,a_n$。

• 因此我们可以使用线段树维护原数组a对应的差分数组b（$b[i] = a[i]-a[i-1]$），求解差分数组的最大公约数等价于求解原数组的最大公约数。

• 当我们要求解a[L, R]的最大公约数时，我们返回gcd(a[L], gcd(b[L+1]~b[R]))即可。

• 当我们给区间[L, R]增加一个数时，我们只需要修改b[L]和b[R+1]的值即可，这样我们的操作就变成了单点修改，区间查询的问题了，不需要用到pushdown操作了。

• 对于gcd(a[L], gcd(b[L+1]~b[R]))中的a[L]的求解，相当于区间修改，单点查询的问题，这对应AcWing 242. 一个简单的整数问题，可以参考本题的分析：网址。可以使用树状数组或者线段树求解，两者都需要将a转为差分数组。这样对a[L]的求解就可以转换为单点修改，区间查询的问题了。

• 为了维护a[L]的值，每个节点还需要存储另外一个变量sum，如下：

struct Node {
    int l, r;
    int d;  // 区间a[l, r]之间数据的最大公约数,等价于b[l, r]之间数据的最大公约数
    int sum;  // sum = b[r] + b[r-1] + ... + b[l]
}

• 现在考虑我们能不能使用上述信息从子节点得到父节点的sum值呢？答案是可以的，父节点的sum等于两个子节点的sum之和。

• 至此，本题分析完毕。

#include <iostream>

using namespace std;

typedef long long LL;

const int N = 500010;

int n, m;  // 数组长度、指令数目
LL a[N];  // a是输入数组, b是a对应的差分数组
struct Node {
    int l, r;
    LL sum;  // sum = b[r] + b[r-1] + ... + b[l]
    LL d;  // 区间a[l, r]之间数据的最大公约数,等价于b[l, r]之间数据的最大公约数
} tr[N * 4];

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.d = gcd(l.d, r.d);
}

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) {
        LL b = a[r] - a[r - 1];
        tr[u] = {l, r, b, b};
    } else {
        tr[u].l = l, tr[u].r = 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) {
        LL b = tr[u].sum + v;
        tr[u] = {x, x, b, b};
    } 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 (tr[u].l >= 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 {
            auto left = query(u << 1, l, r);
            auto right = query(u << 1 | 1, l, r);
            Node res;
            pushup(res, left, right);
            return res;
        }
    }
}

int main() {

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

    build(1, 1, n);

    int l, r;
    LL d;  // 加上的数
    char op[2];  // 操作
    while (m--) {
        scanf("%s%d%d", op, &l, &r);
        if (*op == 'Q') {
            auto left = query(1, 1, l);  // 为了得到a[l]的值，即a[l]=left.sum
            Node right({0, 0, 0, 0});
            if (l + 1 <= r) right = query(1, l + 1, r);  // 为了得到a[l+1~r]的最大公约数
            printf("%lld\n", abs(gcd(left.sum, right.d)));
        } else {
            scanf("%lld", &d);
            modify(1, l, d);
            if (r + 1 <= n) modify(1, r + 1, -d);
        }
    }

    return 0;
}