线段树支持标记和标记的合并，值和值的合并，标记和值的合并。
维护原序列的话，不知道打了区间修改的标记后gcd的变化。
转化为差分序列后，单点修改区间查询gcd。时间复杂度nlogn
gcd(a,b)=gcd(a,b-a)
const int maxn=500010; int n,m; ll w[maxn]; struct node{ int l,r; ll sum,d; }tr[maxn*4]; ll gcd(ll a,ll b){ return b==0?a:gcd(b,a%b); } 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 tmp=w[r]-w[r-1]; tr[u].l=l;tr[u].r=r; tr[u].d=tmp;tr[u].sum=tmp; } 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 update(int u,int x,ll v){ if(tr[u].l==x&&tr[u].r==x){ ll tmp=tr[u].sum+v; tr[u].l=x;tr[u].r=x; tr[u].d=tmp;tr[u].sum=tmp; } else{ int mid=tr[u].l+tr[u].r>>1; if(x<=mid) update(u<<1,x,v); else update(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{ node left=query(u<<1,l,r); node right=query(u<<1|1,l,r); node res; pushup(res,left,right); return res; } } } int main(){ n=read();m=read(); for(int i=1;i<=n;i++) w[i]=read(); build(1,1,n); int x,y;char op[2]; while(m--){ cin>>op;x=read();y=read(); if(op[0]=='Q'){ node left=query(1,1,x),right=query(1,x+1,y); printf("%lld\n",abs(gcd(left.sum,right.d))); } else{ ll d;d=read(); update(1,x,d); if(y+1<=n) update(1,y+1,-d); } } return 0; }
