题目描述

这道题目关键点在于区间修改
一般来讲是要使用懒标记的
但是由于gcd的特殊性，我们可以有一种简便方法
根据更相减损术，gcd(x,y)=gcd(x,y-x)

简易证明：
设x=k1*gcd(x,y),y=k2*gcd(x,y)
则k1,k2互质
y-x=(k2-k1)*gcd(x,y)
(k2-k1)与k1依然互质
故gcd(x,y)=gcd(x,y-x)
证毕

那么这个操作有什么好处呢？
假如我们对需要求gcd的区间都做这样一个处理
那么当这个区间的初值同时改变时，相邻数字差值并不会改变
当然，第一个数会改变，而区间后的第一个数也会改变
比如： a1,a2,a3,a4,a5,a6
经过处理变为：a1,a2-a1,a3-a2,a4-a3,a5-a4,a6-a5
若把a3~a5均加上x
那么会变为a1,a2-a1,a3-a2+x,a4-a3,a5-a4,a6-a5-x
变化的原因是a3变大了，而a2没变，a5变大了，而a6没变
所以我们就省去了区间修改的操作

而当我们计算某一区间gcd时，只需求gcd(a[l],ask(1,l+1,r))
ask(1,l+1,r)代表线段树所维护的经过处理之后数组的gcd

这时我们会遇到一个问题，a[l]怎么求？
经过多次区间修改，总不能暴力求吧？
若是用线段树，依然要使用懒标记
所以我们需要了解一个树状数组的特殊操作来修改区间
树状数组本身只支持单点修改
但是可以对于你维护的数组，再新开一个数组来表示其变化
初值全赋为0代表未变化过，当对某一区间改变时
对区间第一个值加上变化量x，区间后第一个值减去x
这样的话对于新数组，期望修改的区间内每一位置的前缀和都增加x
所以维护前缀和即可知道每一位置的该变量
而从区间后第一位开始，又会消除这份影响

C++ 代码

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<stack>
#include<cmath>
#include<string>
#include<cstring>
using namespace std;
typedef long long ll;
ll a[500010],b[500010],c[500010];
ll lowbit(ll n){
    return n&(-n);
}//这个操作没用上 
ll gcd(ll a,ll b){
    return b==0?abs(a):abs(gcd(b,a%b));
}
struct node{
    ll l,r;
    ll dat;
}t[2000050];
//正常建树即可，存区间gcd 
void build(ll p,ll l,ll r){
    t[p].l=l;
    t[p].r=r;
    if(l==r){
        t[p].dat=b[l];
        return ;
    }
    ll mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    t[p].dat=gcd(t[p*2].dat,t[p*2+1].dat);
}
//修改单点值，正常修改并把gcd向上传即可 
void change(ll p,ll x,ll v){
    if(t[p].l==t[p].r){
        t[p].dat+=v;
        return ;
    }
    if(x<t[p].l||x>t[p].r)
        return ;
    ll mid=(t[p].l+t[p].r)/2;
    if(x<=mid)
        change(p*2,x,v);
    else
        change(p*2+1,x,v);
    t[p].dat=gcd(t[p*2].dat,t[p*2+1].dat);
}
//同样正常查询即可 
ll ask(ll p,ll l,ll r){
    if(l<=t[p].l&&r>=t[p].r)
        return t[p].dat;
    ll mid=(t[p].l+t[p].r)/2;
    ll val=0;
    if(l<=mid)
        val=gcd(val,ask(p*2,l,r));
    if(r>mid)
        val=gcd(val,ask(p*2+1,l,r));
    return val;
}
/*
接下来是对树状数组的操作
数组c是用来记录区间修改的影响的
初值全赋为0
当某一区间，例如[l,r]同时增加x时
给c[l]增加x，c[r+1]减x
这样做的效果是c数组[l,r]内每一位的前缀和都会增加x
而从r+1开始，又会消除这个影响
所以查询a[i]的值，只需要看c[1~i]即可知道该值有没有变化
故维护c数组的前缀和 
*/ 
ll ask1(ll x){//查询c数组前x个数的和 
    ll ans=0;
    for(;x;x-=x&-x)
        ans+=c[x];
    return ans;
}
void add(ll x,ll y,ll n){//c[x]+y，并且维护树状数组之后的值 
    for(;x<=n;x+=x&-x)
        c[x]+=y;
}
string s;
int main(){
    ll n,m;
    memset(c,0,sizeof(c));
    scanf("%lld %lld",&n,&m);
    for(ll i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    for(ll i=1;i<=n;i++)
        b[i]=a[i]-a[i-1];
    build(1,1,n);
    ll l,r,d;
    while(m--){
        cin>>s;
        if(s[0]=='C'){
            scanf("%lld %lld %lld",&l,&r,&d);
            //线段树维护的gcd需要修改 
            change(1,l,d);
            change(1,r+1,-d);
            //树状数组维护的c数组前缀和也需要修改 
            add(l,d,n);
            add(r+1,-d,n);
        }
        else if(s[0]=='Q'){
            scanf("%lld %lld",&l,&r);
            //ask1(l)即表示a[l]的变化量 
            printf("%lld\n",gcd(a[l]+ask1(l),ask(1,l+1,r)));
        }
    }
}