题意：给定一个长度为 NN 的数列 AA，以及 MM 条指令，每条指令可能是以下两种之一：

  1. C l r d，表示把 A[l],A[l+1],…,A[r]A[l],A[l+1],…,A[r] 都加上 dd。

  2. Q l r，表示询问 A[l],A[l+1],…,A[r]A[l],A[l+1],…,A[r] 的最大公约数。

对于每个询问，输出一个整数表示答案。

求最大公约数，容易想到更相减损法，即 gcd⁡(a,b)=gcd⁡(b,a−b)\gcd (a,b)= \gcd (b,a-b)，同理，这个方法可以扩展到多个数，即 gcd⁡(a,b,c)=gcd⁡(a,b−a,c−b)\gcd (a,b,c)= \gcd (a,b-a,c-b)，所以我们可以先用一个 b 数组来记录 a 的差分数组，然后用线段树维护这个 b 数组的最大公约数，那么就可以得到第二个操作的答案为 gcd⁡(A[l],query(l+1,r))\gcd (A[l],query(l+1,r))。

由于答案中要用到现在 A[l]A[l] 的值，而 A[l]A[l] 的值同时会变化，我们同时开一个树状数组维护差分数组记录变化值即可，第一个区间修改的操作也可以方便的通过修改端点的方式利用差分数组完成。

所以我们只用维护一个需要求区间 gcd，单点修改的线段树和一个普通树状数组即可。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
using namespace std;
long long n,m;
long long a[501010],b[501010];
long long num[2001010],tree[501010];
long long lowbit(long long x)
{
	return x&(-x);
}
void update(long long x,long long val)
{
	for(int i=x;i<=n;i+=lowbit(i))
		tree[i]+=val;
}
long long ask(long long x)
{
	long long sum=0;
	for(int i=x;i;i-=lowbit(i))
		sum+=tree[i];
	return sum;
}
long long gcd(long long a,long long b)
{
	if(b==0)
		return a;
	return gcd(b,a%b);
}
void pushup(long long rt)
{
	num[rt]=gcd(num[rt<<1],num[rt<<1|1]);
}
void build(long long l,long long r,long long rt)
{
	if(l==r)
	{
		num[rt]=b[l];
		return ;
	}
	long long mid=(l+r)>>1;
	build(lson);
	build(rson);
	pushup(rt);
}
void add(long long p,long long val,long long l,long long r,long long rt)
{
	if(l==r)
	{
		num[rt]+=val;
		return ;
	}
	long long mid=(l+r)>>1;
	if(p<=mid)
		add(p,val,lson);
	else
		add(p,val,rson);
	pushup(rt);
}
long long query(long long L,long long R,long long l,long long r,long long rt)
{
	if(L<=l&&r<=R)
		return num[rt];
	long long mid=(l+r)>>1;
	long long val=0;
	if(L<=mid)
		val=gcd(val,query(L,R,lson));
	if(R>mid)
		val=gcd(val,query(L,R,rson));
	return abs(val);
}
int main()
{
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		b[i]=a[i]-a[i-1];
	}
	build(1,n,1);
	while(m--)
	{
		char s[2];
		scanf("%s",s);
		long long l,r,d;
		scanf("%lld%lld",&l,&r);
		if(s[0]=='C')
		{
			scanf("%lld\n",&d);
			add(l,d,1,n,1);
			if(r<n)
				add(r+1,-d,1,n,1);
			update(l,d);
			update(r+1,-d);
		}
		else
		{
			scanf("\n");
			long long ans1=a[l]+ask(l);
			long long ans2=l<r?query(l+1,r,1,n,1):0;
			printf("%lld\n",gcd(ans1,ans2));
		}
	}
	return 0;
}