题目描述
给定一个长度为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)。
“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的正整数。
gcd(x,y)=gcd(x,y-x),gcd(x,y,z)=gcd(x,y-x,z-y)……对任意多个整数都成立 将A数列进行查分，线段树维护差分序列的最大公约数，每次询问就是gcd(A[l],query(,,n,l+,r);
每次修改update(1,1,n,l,d),update(1,1,n,r+1,-d)
A数组也需要维护，线段树和树状数组都行
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5e5+;
ll A[N*],a[N],B[N*],b[N];
int n,m;
char op;
int lowbit(int x)
{
return x&-x;
}
void add(int x,ll val)
{
for (int i=x;i<=n;i+=lowbit(i))
A[i]+=val;
}
ll sum(int x)
{
ll ret=;
for (int i=x;i>=;i-=lowbit(i))
ret+=A[i];
return ret;
}
void Pushup(int s)
{
B[s]=__gcd(B[s<<],B[s<<|]);
}
void build(int s,int l,int r)
{
if (l==r)
{
B[s]=b[l];
return ;
}
int mid=(l+r)>>;
build(s<<,l,mid);
build(s<<|,mid+,r);
Pushup(s);
}
void update(int s,int l,int r,int pos,ll val)
{
if (l==r)
{
B[s]+=val;
return ;
}
int mid=(l+r)>>;
if (pos<=mid) update(s<<,l,mid,pos,val);
else update(s<<|,mid+,r,pos,val);
Pushup(s);
}
ll query(int s,int l,int r,int L,int R)
{
// cout<<s<<' '<<l<<' '<<r<<' '<<L<<' '<<R<<' '<<B[s]<<endl; if (L<=l&&r<=R) return B[s]; int mid=(l+r)>>;
if (R<=mid) return query(s<<,l,mid,L,R);
else if (L>mid) return query(s<<|,mid+,r,L,R);
else return __gcd(query(s<<,l,mid,L,R),query(s<<|,mid+,r,L,R));
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=;i<=n;i++) scanf("%lld",&a[i]);
for (int i=;i<=n;i++) b[i]=a[i]-a[i-],add(i,b[i]); build(,,n);
int l,r; ll d;
while (m--)
{ scanf(" %c",&op);
if (op=='C')
{
scanf("%d%d%lld",&l,&r,&d);
add(l,d);
add(r+,-d);
update(,,n,l,d);
if (r+<=n) update(,,n,r+,-d);
}
else
{
scanf("%d%d",&l,&r);
//cout<<sum(l)<<endl;
//cout<<query(1,1,n,r,r)<<endl;
//cout<<query(1,1,n,l+1,r)<<endl;
ll ans=abs(__gcd(sum(l),query(,,n,l+,r)));
printf("%lld\n",ans);
}
}
return ;
}