题目大意：给定一个长度为 N 的序列，M 个操作，支持区间加，区间查询最大公约数。
题解：
先来看一个子问题，若是单点修改，区间最大公约数，则可以发现，每次修改最多改变 \(O(logn)\) 个答案，且 gcd 可以合并，因此可以直接在线段树上维护。
但是对于区间加来说，无法在已知区间加了某一个数时快速计算出新的区间最大公约数，因此，最坏情况下复杂度可能退化到 \(O(n)\)。考虑辗转相除法的性质，$$gcd(x,y,z)=gcd(x,y-x,z-y)$$可以发现，若维护的是原序列的差分序列，则问题会转化成上述子问题。且原问题询问的答案为$$gcd(a[l],query(l+1,r))$$，即可保证复杂度不退化。另外，要维护原序列的值，可以采用树状数组在差分数组上进行单点修改、区间查询即可。
代码如下
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5e5+10;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int n,m;char s[4];
ll a[maxn],b[maxn],bit[maxn];
inline void change(int pos,ll val){
for(int i=pos;i<=n;i+=i&-i)bit[i]+=val;
}
inline ll get(int pos){
ll ret=0;
for(int i=pos;i;i-=i&-i)ret+=bit[i];
return ret;
}
struct node{
#define ls(o) t[o].lc
#define rs(o) t[o].rc
int lc,rc;ll g;
}t[maxn<<1];
int tot,root;
inline void pushup(int o){t[o].g=gcd(t[ls(o)].g,t[rs(o)].g);}
int build(int l,int r){
int o=++tot;
if(l==r){t[o].g=b[l];return o;}
int mid=l+r>>1;
ls(o)=build(l,mid),rs(o)=build(mid+1,r);
return pushup(o),o;
}
void modify(int o,int l,int r,int pos,ll val){
if(l==r){t[o].g+=val;return;}
int mid=l+r>>1;
if(pos<=mid)modify(ls(o),l,mid,pos,val);
else modify(rs(o),mid+1,r,pos,val);
pushup(o);
}
ll query(int o,int l,int r,int x,int y){
if(l==x&&r==y)return t[o].g;
int mid=l+r>>1;
if(y<=mid)return query(ls(o),l,mid,x,y);
else if(x>mid)return query(rs(o),mid+1,r,x,y);
else return gcd(query(ls(o),l,mid,x,mid),query(rs(o),mid+1,r,mid+1,y));
}
void read_and_parse(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]),b[i]=a[i]-a[i-1];
root=build(1,n);
}
void solve(){
int l,r;ll delta;
while(m--){
scanf("%s%d%d",s,&l,&r);
if(s[0]=='Q'){
ll c=a[l]+get(l),d=l<r?abs(query(root,1,n,l+1,r)):0;
printf("%lld\n",gcd(c,d));
}
else{
scanf("%lld",&delta);
modify(root,1,n,l,delta);
if(r<n)modify(root,1,n,r+1,-delta);
change(l,delta);
if(r<n)change(r+1,-delta);
}
}
}
int main(){
read_and_parse();
solve();
return 0;
}