AcWing 246. Interval maximum common divisor
Given A sequence A with length N and M instructions, each instruction may be one of the following two:
C l r d means adding d to A[l],A[l+1],..., A[r].
Q l r, represents the maximum common divisor (GCD) of query A[l],A[l+1],..., A[r].
For each query, an integer is output to represent the answer.

Input format
The first line contains two integers N,M.
The second line contains N integers A[i].
Next, line M represents m instructions, and the format of each instruction is shown in the title description.

Output format
For each query, an integer is output to represent the answer.
One line for each answer.

Data range
N≤500000,M≤100000,
1≤A[i]≤10^18,
|d|≤10^18

Input example:
5 5
1 3 5 7 9
Q 1 5
C 1 5 1
Q 1 5
C 3 3 6
Q 2 4
Output example:
1
2
4

Knowledge points:
1.gcd(a,b)=gcd(a,b−a)
More phase subtraction is a special case of Euclidean algorithm, which can be extended to the case of multiple numbers.
gcd(a1,a2,a3,..., an)=gcd(a1,a2-a1,a3-a2,..., an-an-1)
With this formula, we can achieve the same effect of gcd by maintaining the difference of the sequence.
To find (a,b,c), you only need to know the current value of a, then the gcd of (B − a,c − b), and then find a common divisor
Difference can turn interval addition and subtraction into single point addition and subtraction. You can use a line segment tree without lazy. Then maintain a difference and make it into a tree array or line segment tree to maintain the value of each number.

2.gcd(a,b)=gcd(a,−b)
Negative numbers may be generated in the process of numerical addition and subtraction, but the Convention gcd has no negative numbers, so we need to use this formula to deal with negative numbers.
Specifically, if a negative number is encountered during each query or update, it is reversed.
Note that you can only take the result, but you can't directly take the negative leaf node of the line segment tree inversely. Because the direct inversion of leaves will affect the addition and subtraction operation in the future.
gcd(a,b)=gcd(a, − b), but (a+1,b) and (− a+1,b) are not necessarily equal.

#include<bits/stdc++.h>
using namespace std;
template <typename T> void debug(string s, T x) { cout << s << "=" << x << "\n"; }
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>pll;
typedef pair<int, int>pii;
const int INF = 0x7fffffff;
const int N = 5e5 + 5;
ll w[N];
struct node {
    ll l, r;
    ll d;
    ll sum;
}tree[N << 2];
void push_up(ll root) {
    tree[root].d = __gcd(tree[root << 1].d, tree[root << 1 | 1].d);//When updating node information, only the maximum value is required
    tree[root].sum = tree[root << 1].sum + tree[root << 1 | 1].sum;
}
void build(ll root, ll l, ll r) {
    if (l == r)tree[root] = { l,r,w[r]-w[r-1],w[r]-w[r-1] };
    else {
        tree[root] = { l,r };
        ll mid = l + r >> 1;
        build(root << 1, l, mid);
        build(root << 1 | 1, mid + 1, r);
        push_up(root);
    }
}
void modify(ll root, ll pos, ll num) {
    if (tree[root].l == pos && tree[root].r == pos) {
        ll b = tree[root].sum + num;
        tree[root] = { pos,pos,b,b };
    }
    else {
        ll mid = tree[root].l + tree[root].r >> 1;
        if (pos <= mid)modify(root << 1, pos, num);
        else modify(root << 1 | 1, pos, num);
        push_up(root);
    }
}
node query(ll root, ll l, ll r) {
    if (tree[root].l >= l && tree[root].r <= r)return tree[root];
    
    ll mid = tree[root].l + tree[root].r >> 1;
    if (r<=mid)return query(root << 1, l, r);
    else if (l>mid)return query(root << 1 | 1, l, r);
    else {
        node left = query(root << 1, l, r);
        node right = query(root << 1 | 1, l, r);
        node ans;
        ans.sum = left.sum + right.sum;
        ans.d = __gcd(left.d , right.d);
        return ans;
    }
}
int main() {
    ios_base::sync_with_stdio(false), cin.tie(0);

    ll n, m;
    cin >> n >> m;
    for (ll i = 1; i <= n; i++)cin >> w[i];
    build(1, 1, n);
    while (m--) {
        string s;
        cin >> s;
        if (s[0] == 'C') {
            ll l, r, d;
            cin >> l >> r >> d;
            modify(1, l, d);
            if (r + 1 <= n)modify(1, r + 1, -d);
        }
        else {
            ll l, r;
            cin >> l >> r;
            node left = query(1, 1, l);
            node right = { 0,0,0,0 };
            if (l + 1 <= r)right = query(1, l + 1, r);
            cout << abs(__gcd(left.sum, right.d))<<"\n";
        }
    }
    return 0;
}