bzoj 5028: 小Z的加油店

.

题意：有n个瓶子排成一排，两种操作：1：用l到r的瓶子倒出最少的油（不能不倒）2：l到r的容量+x。
题解：首先，一段瓶子能倒出的最少的油就是它们容量的最大公约数（裴蜀定理）。差分一下，很明显$\gcd(v_l,v_{l+1},v_{l+2}\dots v_r)=gcd(v_l,v_{l+1}-v_l,v_{l+2}-v_{l+1}\dots v_r-v_{r-1})$所以我们只需用线段树维护差分后的v的gcd和前缀和就好了。
代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n,m,a[100010],num=0;
struct tree
{
    int l,r,lc,rc,c1,c2;
}tr[200010];

int gcd(int x,int y)
{
    return y==0?x:gcd(y,x%y);
}
void pushup(int x)
{
    int lc=tr[x].lc,rc=tr[x].rc;
    tr[x].c1=tr[lc].c1+tr[rc].c1;
    tr[x].c2=gcd(tr[lc].c2,tr[rc].c2);
}
int bt(int l,int r)
{
    int i=++num;
    tr[i].l=l;
    tr[i].r=r;
    if(l<r)
    {
        int md=l+r>>1;
        tr[i].lc=bt(l,md);
        tr[i].rc=bt(md+1,r);
        pushup(i);
    }
    else
    tr[i].c1=tr[i].c2=a[l]-a[l-1];
    return i;
}
void chg(int i,int x,int p)
{
    if(tr[i].l==tr[i].r)
    {
        tr[i].c1=tr[i].c2+=x;
        return;
    }
    int md=tr[i].l+tr[i].r>>1,lc=tr[i].lc,rc=tr[i].rc;
    if(p<=md)
    chg(lc,x,p);
    else
    chg(rc,x,p);
    pushup(i);
}
int get1(int i,int l,int r)
{
    if(l>r)
    return 0;
    if(tr[i].l==l&&tr[i].r==r)
    return tr[i].c1;
    int md=tr[i].l+tr[i].r>>1,lc=tr[i].lc,rc=tr[i].rc;
    if(r<=md)
    return get1(lc,l,r);
    else if(l>md)
    return get1(rc,l,r);
    else
    return get1(lc,l,md)+get1(rc,md+1,r);
}
int get2(int i,int l,int r)
{
    if(l>r)
    return 0;
    if(tr[i].l==l&&tr[i].r==r)
    return tr[i].c2;
    int md=tr[i].l+tr[i].r>>1,lc=tr[i].lc,rc=tr[i].rc;
    if(r<=md)
    return get2(lc,l,r);
    else if(l>md)
    return get2(rc,l,r);
    else
    return gcd(get2(lc,l,md),get2(rc,md+1,r));
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    scanf("%d",&a[i]);
    bt(1,n);
    for(int i=0;i<m;i++)
    {
        int f,l,r;
        scanf("%d%d%d",&f,&l,&r);
        if(l>r)
        swap(l,r);
        if(f==1)
        printf("%d\n",abs(gcd(get1(1,1,l),get2(1,l+1,r))));
        else
        {
            int x;
            scanf("%d",&x);
            chg(1,x,l);
            if(r<n)
            chg(1,-x,r+1);
        }/*
        for(int i=1;i<=n;i++)
        {
            printf("%d ",getnum(i));
        }
        puts("");
        for(int i=1;i<=num;i++)
        printf("%d %d %d\n",tr[i].l,tr[i].r,tr[i].c);*/
    }
}