BZOJ 5028 小z的加油站

电玩女神 2021-11-02 00:22 259阅读 0赞

[bzoj链接][bzoj]

Time limit 10000 ms  
Memory limit 262144 kB  
OS Linux

## 感想 ##

树上动态gcd的第二题也好了。

*  \[x\] BZOJ 2257 \[[JSOI2009\]瓶子和燃料][JSOI2009]
 *  \[x\] BZOJ 5028 [小z的加油站][z]
 *  \[ \] CodeChef DGCD [Dynamic GCD][]

## 解题思路 ##

由上一题 [\[JSOI2009\]瓶子和燃料][JSOI2009] 可知，这题这样子折腾就是在求区间最大公因数，这里还带上了区间加，所以需要另外一些性质——

参考了[这篇博客][Link 1]。

众所周知，区间加作用到原序列上，相当于差分序列的两次单点修改（操作范围的右边顶着边界，那就是1次单点修改）。由更相减损可知，原序列总的gcd等于差分序列总的gcd，即差分一下gcd不变（此时求gcd的函数要注意将小于零的参数换成其绝对值进行计算，因为更相减损是大的减小的）。

> \\\[\\gcd\\left(a\_\{1\}, a\_\{2\}, a\_\{3\}, \\dots, a\_\{n-2\}, a\_\{n-1\}, a\_\{n\}\\right)\\\]
> 
> \\\[=\\gcd \\left(a\_\{1\}, a\_\{2\}-a\_\{1\}, a\_\{3\}-a\_\{2\}, \\ldots a\_\{n-1\}-a\_\{n-2\}, a\_\{n\}-a\_\{n-1\}\\right)\\\]

设\\(a\_0=0\\)，\\(d\_i=a\_i-a\_\{i-1\}\\)（差分数组），于是把上式推广到其他区间——

> \\\[\\gcd\\left(a\_\{l\}, a\_\{l+1\}, a\_\{l+2\}, \\dots, a\_\{r-2\}, a\_\{r-1\}, a\_\{r\}\\right)\\\]  
> \\\[=\\gcd\\left( a\_\{l\} , \\gcd (d\_\{l+1\}, d\_\{l+2\}, \\ldots, d\_\{r\})\\right)\\\]  
> \\\[=\\gcd\\left(\\sum\_\{i=1\}^\{l\} d\_\{l\} , \\gcd \\left(d\_\{l+1\}, d\_\{l+2\}, \\ldots, d\_\{r\}\\right)\\right)\\\]

又因为gcd满足区间加法，于是，我们就可以用线段树维护差分序列的区间和、gcd。

顺便，Hint里出现的那个\\(L>R\\)意思应该不是说数据有锅，而是说，当查询的区间长度为1时，要注意特判。  
观察上式——\\\[\\gcd\\left(\\sum\_\{i=1\}^\{l\} d\_\{l\} , \\gcd \\left(d\_\{l+1\}, d\_\{l+2\}, \\ldots, d\_\{r\}\\right)\\right)\\\]  
对于这一项\\\[\\gcd \\left(d\_\{l+1\}, d\_\{l+2\}, \\ldots, d\_\{r\}\\right)\\\]  
当\\(l=r\\)，即查询区间长度为1时，会出现\\(l+1>r\\)的情况，此时这一项应该直接返回0，以防止干扰结果。或者在其他地方特判一下也行。

## 源代码 ##

#include<stdio.h>
    
    const int MAXN=1e5+5;
    long long gcd(long long x,long long y)
    {
        if(x<0) x=-x;
        if(y<0) y=-y;
        return y==0?x:gcd(y,x%y);
    }//更相减损是大的减小的
    int n,m;
    long long d[MAXN];//差分数组
    
    struct Segtree{
        long long g,sum;
    }t[MAXN<<2];//维护差分数组的线段树
    void pushup(int x)
    {
        t[x].g=gcd(t[x<<1].g,t[x<<1|1].g);
        t[x].sum=t[x<<1].sum+t[x<<1|1].sum;
    }
    void build(int x,int l,int r)
    {
        if(l==r)
        {
            t[x].g=t[x].sum=d[l];
            return;
        }
        int mid=l+r>>1;
        build(x<<1,l,mid);
        build(x<<1|1,mid+1,r);
        pushup(x);
    }
    void update(int x,int l,int r,int pos,int k)//pos处增加k
    {
        if(l==r)
        {
            t[x].sum+=k;
            t[x].g+=k;
            return;
        }
        int mid=l+r>>1;
        if(pos<=mid) update(x<<1,l,mid,pos,k);
        else update(x<<1|1,mid+1,r,pos,k);
        pushup(x);
    }
    long long quesum(int x,int l,int r,int ql,int qr)
    {
        if(ql<=l&&r<=qr)
            return t[x].sum;
        long long ans=0;
        int mid=l+r>>1;
        if(ql<=mid) ans+=quesum(x<<1,l,mid,ql,qr);
        if(qr>mid) ans+=quesum(x<<1|1,mid+1,r,ql,qr);
        return ans;
    }
    long long quegcd(int x,int l,int r,int ql,int qr)
    {
        if(ql>qr) return 0;//特判这个
        if(ql<=l&&r<=qr)
            return t[x].g;
        long long ans;
        int mid=l+r>>1;
        if(qr<=mid) ans=quegcd(x<<1,l,mid,ql,qr);
        else if(ql>mid) ans=quegcd(x<<1|1,mid+1,r,ql,qr);
        else ans=gcd(quegcd(x<<1,l,mid,ql,qr),quegcd(x<<1|1,mid+1,r,ql,qr));
        return ans;
    }
    
    inline long long opt1(int l,int r)//区间询问gcd
    {
        return gcd(quesum(1,1,n,1,l),quegcd(1,1,n,l+1,r));
    }
    void opt2(int l,int r,int k)//区间增加k
    {
        update(1,1,n,l,k);
        if(r<n) update(1,1,n,r+1,-k);
    }
    int main()
    {
        //freopen("test.in","r",stdin);
        scanf("%d%d",&n,&m);
        d[0]=0;
        for(int i=1;i<=n;i++)
            scanf("%lld",d+i);
        for(int i=n;i>1;i--) 
            d[i]-=d[i-1];
        build(1,1,n);
        while(m--)
        {
            int opt,l,r,k;
            scanf("%d%d%d",&opt,&l,&r);
            if(opt==1)
            {
                printf("%lld\n",opt1(l,r));
            }
            else
            {
                scanf("%d",&k);
                opt2(l,r,k);
            }
        }
        return 0;
    }

转载于:https://www.cnblogs.com/wawcac-blog/p/11317690.html

[bzoj]: https://vjudge.net/problem/1765470/origin
[JSOI2009]: https://www.cnblogs.com/wawcac-blog/p/11315717.html
[z]: https://www.cnblogs.com/wawcac-blog/p/11317690.html
[Dynamic GCD]: https://www.cnblogs.com/wawcac-blog/p/11321076.html
[Link 1]: https://blog.csdn.net/m0_38081836/article/details/81608721