246. 区间最大公约数(线段树+树状数组)

一时失言乱红尘 2021-11-05 19:52 340阅读 0赞

题目链接：[https://www.acwing.com/problem/content/247/][https_www.acwing.com_problem_content_247]  
给定一个长度为N的数列A，以及M条指令，每条指令可能是以下两种之一：

1、“C l r d”，表示把 A\[l\],A\[l+1\],…,A\[r\] 都加上 d。

2、“Q l r”，表示询问 A\[l\],A\[l+1\],…,A\[r\] 的最大公约数(GCD)。

对于每个询问，输出一个整数表示答案。  
输入格式

第一行两个整数N,M。

第二行N个整数A\[i\]。

接下来M行表示M条指令，每条指令的格式如题目描述所示。  
输出格式

对于每个询问，输出一个整数表示答案。

每个答案占一行。  
数据范围

N≤500000,M≤100000

输入样例：

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

分析：今天的开头顺了。虽然花了挺久的时间，但是通过不断地调整后，终于过了样例，然后就一发了。 没wa 超开心。  
题目要求的目的：区间操作，区间查询。

做这个题一定要知道一个定理：[九章算术之更相减损术][Link 1]  
gcd(x,y)=gcd(x,y-x)。  
当然，此结论可用数学归纳法推广到一般，该性质对多个整数都成立。  
即：gcd(x,y,z,…)=gcd(x,y-x,z-y,…)。

我们观察上述式子，可发现对于一个gcd(x,y-x,z-y,…)，把第一项不看。剩下的几项就是一个差分数列。那么我们可得：gcd(x,y-x,z-y,…)　＝gcb(x,gcb(y-x,z-y……) )。  
也就是说，我们通过线段树来维护差分序列的gcb值。然后在把此gcb值和x进行求公差运算。  
又因为x也是会变化的。所以x的值我们肯定是需要维护的。在看题目的操作  
C l r d 是把l - r 这个区间都加上d（区间操作）。到此，我们发现这个维护x的值就很简单了（用树状数组维护），[不懂可参考][Link 2]。

所以，我们目前还未解决的问题就是如何维护gcb(y-x,z-y……)。在这里采用的是线段树维护。具体见代码。

注意点：  
１，在不断的对区间操作的过程中，差分数列的值是可能变成负数的。这个时候我们求gcb的函数，需要稍作改变，切记不可直接把负数变成正数。  
因为直接把叶子取反会对今后的加减操作造成影响。  
虽然gcd(a,b)=gcd(a,−b)但是(a+1,b)和(a+1,−b)不一定相等。  
2，数据范围爆int。

#include"stdio.h"
    #include"string.h"
    #include"math.h"
    #include"algorithm"
    using namespace std;
    typedef long long ll;
    #define Max (ll)1e5 + 23
    
    typedef struct Node
    {
        ll  val,gcb;
        ll l,r;
    }Node;
    
    ll C[Max],N,M,a[Max],b[Max],G;
    Node node[4 * Max];
    
    ll Gcb(ll x,ll y)
    {
        if(x < 0) x = -x; if(y < 0) y = -y;/// 把负数先变成正数
        if(x < y) swap(x,y);
        if(y == 0) return x;
        return Gcb(y,x % y);
    }
    
    void Build_Tree(ll id,ll l,ll r)
    {
        node[id].l = l; node[id].r = r;
        if(l == r)
        {
            node[id].gcb = b[l]; return ;
        }
        ll mid = (l + r) >> 1;
        Build_Tree(id << 1,l,mid);
        Build_Tree(id << 1 | 1,mid + 1,r);
        node[id].gcb = Gcb(node[id << 1].gcb,node[id << 1 | 1].gcb);
    }
    
    void Update(ll id,ll l,ll r,ll x,ll v)
    {
        if(x > N) return ;
        if(l == r)
        {
            node[id].gcb += v; return ;
        }
        ll mid = (l + r) >> 1;
        if(x <= mid) Update(id << 1,l,mid,x,v);
        else Update(id << 1 | 1,mid + 1,r,x,v);
        node[id].gcb = Gcb(node[id << 1].gcb,node[id << 1 | 1].gcb);
    }
    
    ll Query(ll id,ll l,ll r)
    {
        ll Left = node[id].l,Right = node[id].r;
        ll A = 0,B = 0;
        if(l <= Left && r >= Right) return abs(node[id].gcb);
        ll mid = (Left + Right) >> 1;
        if(l <= mid) A = Query(id << 1,l,r);
        if(r > mid) B = Query(id << 1 | 1,l,r);
        return G = abs(Gcb(A,B));
    }
    ///下面三个函数是对树状数组的维护
    ll lowbit(ll x)
    {  return x & (-x); }
    
    void add(ll x,ll v)
    {
        while(x <= N) {C[x] += v; x += lowbit(x);  }
    }
    
    ll query(ll x)
    {
        ll sum = 0; while(x >= 1) {sum += C[x]; x -= lowbit(x); }
        return sum;
    }
    
    void init()
    {
        scanf("%lld%lld",&N,&M);
        for(int i = 0;i <= N; i ++) C[i] = 0;
        for(int i = 1; i <= N; i ++)
        {
            scanf("%lld",&a[i]);
            b[i] = a[i] - a[i - 1];
        }
        Build_Tree((ll)1,(ll)1,N);
    }
    int main()
    {
        init();
        while(M --)
        {
            char str[10];
            scanf("%s",str);
            if(str[0] == 'Q')
            {
                ll l,r;
                scanf("%lld%lld",&l,&r);
                ll sum = Gcb(query(l) + a[l],Query((ll)1,l + 1,r));
                printf("%lld\n",sum);
            }
            else
            {
                ll l,r,d;
                scanf("%lld%lld%lld",&l,&r,&d);
                add(l,d); add(r + 1,-d);
                Update((ll)1,1LL,N,l,d); Update(1LL,1LL,N,r + 1,-d);
            }
        }
    }

[https_www.acwing.com_problem_content_247]: https://www.acwing.com/problem/content/247/
[Link 1]: https://baike.baidu.com/item/%E6%9B%B4%E7%9B%B8%E5%87%8F%E6%8D%9F%E6%9C%AF/449183?fr=aladdin
[Link 2]: https://blog.csdn.net/qq_43506138/article/details/98585940