描述
给定一个长度为N的数列A，以及M条指令 (N≤5*10^5, M<=10^5)，每条指令可能是以下两种之一：
“C l r d”，表示把 A[l],A[l+1],…,A[r] 都加上 d。
“Q l r”，表示询问 A[l],A[l+1],…,A[r] 的最大公约数(GCD)。
输入格式
第一行两个整数N,M，第二行N个整数Ai，接下来M行每条指令的格式如题目描述所示。
输出格式
对于每个询问，输出一个整数表示答案。
样例输入
5 5 1 3 5 7 9 Q 1 5 C 1 5 1 Q 1 5 C 3 3 6 Q 2 4
样例输出
1 2 4
数据范围与约定
- N,M≤2*10^5，l<=r，数据保证任何时刻序列中的数都是不超过2^62-1的正整数。
题解：根据更相减损术有
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#define ll long long
using namespace std;
const int maxn = 500005;
int n, m;
ll a[maxn], b[maxn], c[maxn];
struct SegmentTree{int l, r;ll dat;
}t[maxn*4];
ll gcd(ll a, ll b){return b ? gcd(b, a%b) : a;
}
int lowbit(int x){return x & -x;
}
ll get_sum(int x){ll sum = 0;while(x){sum += c[x];x -= lowbit(x);}return sum;
}
void add(int x, ll val){while(x <= n){c[x] += val;x += lowbit(x);}
}
void build(int p, int l, int r){t[p].l = l, t[p].r = r;if(l == r){t[p].dat = b[l];return ;}int mid = (l+r)/2;build(2*p, l, mid);build(2*p+1, mid+1, r);t[p].dat = gcd(t[2*p].dat, t[2*p+1].dat);
}
void change(int p, int x, ll v){if(t[p].l == t[p].r){t[p].dat += v;return ;}int mid = (t[p].l+t[p].r)/2;if(x <= mid) change(2*p, x, v);else change(2*p+1, x, v);t[p].dat = gcd(t[2*p].dat, t[2*p+1].dat);
}
ll ask(int p, int l, int r){if(l <= t[p].l && r >= t[p].r){return abs(t[p].dat);}int mid = (t[p].l + t[p].r)/2;ll val = 0;if(l <= mid) val = gcd(val,ask(2*p, l, r));if(r > mid) val = gcd(val,ask(2*p+1, l, r));return abs(val);
}
int main()
{char ch[2];scanf("%d %d", &n, &m);for(int i = 1; i <= n; i++){scanf("%lld", &a[i]);b[i] = a[i] - a[i-1];}build(1, 1, n);while(m--){int l, r;scanf("%s", ch);scanf("%d %d", &l, &r);if(ch[0] == 'C'){ll d;scanf("%lld", &d);change(1, l, d);if(r < n) change(1, r+1, -d);add(l, d);add(r+1, -d);}else{ll al = a[l] + get_sum(l);ll val = l < r ? ask(1, l+1, r) : 0;printf("%lld\n", gcd(al, val));;}}return 0;
}