1.数列的GCD等于差分的GCD
2.将区间加减转化为差分上的单点修改
#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
#define de(x) cout<<#x<<" = "<<x<<" "
#define deg(x) cout<<#x<<" = "<<x<<endl
using namespace std;
const int N=5e5+10;
int n,m;
struct Node
{
int l,r;
int sum,d;
}tr[4*N];
int w[N];
int gcd(int a,int 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)tr[u]={l,r,w[r]-w[r-1],w[r]-w[r-1]};
else
{
tr[u]={l,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,int v)
{
if(tr[u].l==x&&tr[u].r==x)tr[u]={x,x,tr[u].sum+v,tr[u].sum+v};
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];
int mid=tr[u].l+tr[u].r>>1;
if(r<=mid)return query(u<<1,l,r);
if(l>mid)return query(u<<1|1,l,r);
auto left=query(u<<1,l,r),right=query(u<<1|1,l,r);
Node res;
pushup(res,left,right);
return res;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>w[i];
build(1,1,n+1);
while(m--)
{
string s;
cin>>s;
if(s=="Q")
{
int l,r;
cin>>l>>r;
Node left=query(1,1,l),right={0,0,0,0};
if(l+1<=r)right=query(1,l+1,r);
cout<<abs(gcd(left.sum,right.d))<<endl;
}
else
{
int l,r,d;
cin>>l>>r>>d;
modify(1,l,d);
//if(r+1<=n)
modify(1,r+1,-d);
}
}
return 0;
}