区间最大公约数

思路:求l~r的a数组的gcd,等价于求al与各差分ai的gcd.证明:辗转相除法.
详细的讲下吧.假如d是al,al+1...ar的gcd,那么它一定是al,al+1-al,al+2-al+1...的公约数.同理后面可得前面.
那么原题就可以用线段树维护差分数组的gcd即可.
代码如下:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+10;
ll w[N],s[N];
struct node{
    ll l,r,sum,d;    
}tr[N*4];

void pushup(node &u,node &left,node &right)
{
    u.sum=left.sum+right.sum;
    u.d=__gcd(left.d,right.d);
}

void pushup(ll u)
{
    pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}

void build(ll u,ll l,ll r)
{
    if(l==r)
    {
        tr[u]={l,r,w[l],w[l]};
    }
    else
    {
        tr[u]={l,r};
        ll mid=tr[u].l+tr[u].r>>1;
        build(u<<1,l,mid);
        build(u<<1|1,mid+1,r);
        pushup(u);
    }
}

void modify(ll u,ll x,ll v)
{
    if(tr[u].l==tr[u].r&&tr[u].l==x)
    {
        tr[u]={x,x,tr[u].sum+v,tr[u].sum+v};
        return;
    }
    else
    {
        ll 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(ll u,ll l,ll r)
{
    if(l<=tr[u].l&&tr[u].r<=r)  return tr[u];
    else
    {
        ll 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
        {
            auto left=query(u<<1,l,r);
            auto right=query(u<<1|1,l,r);
            node res;
            pushup(res,left,right);
            return res;
        }
    }
}

int main()
{
    ll n,m;
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&s[i]);
        w[i]=s[i]-s[i-1];
    }
    build(1,1,n);
    while(m--)
    {
        char op[3];
        scanf("%s",op);
        if(op[0]=='C')//l~r 加上 d
        {
            ll l,r,d;
            scanf("%lld%lld%lld",&l,&r,&d);
            modify(1,l,d);
            if(r+1<=n)  modify(1,r+1,-d);
        }
        else//查询l~r的gcd. 
        {
            ll l,r;
            scanf("%lld%lld",&l,&r);
            ll res1=query(1,1,l).sum;
            ll res2=query(1,l+1,r).d;
            printf("%lld\n",abs(__gcd(res1,res2)));
        }
    }
    return 0;
}