interval GCD

interval GCD

题目分析:

1. 把 A[l],A[l+1],…,A[r] 都加上 d

• 利用差分改变区间[l,r]的值

  a[l] += d,a[r + 1] -= d

2. 询问 A[l],A[l+1],…,A[r] 的最大公约数(GCD)

• 根据辗转相除法，gcd(a,b) = gcd(b,a - b),gcd(a,b,c) = gcd(a,b - a,c - b)
• 那么，询问区间[l,r]最大公约数为：

  gcd(query(1,1,l).sum,query(1,l + 1,r).d)

3. 需要维护两个属性：

   ll sum; //sum表示和，求差分区间[l,r]的和，值为a[r]
   ll d;//d为区间[l,r]的最大公约数         

代码如下：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

#define ll long long 

const int N = 5e5 + 10;

int n,m;
ll w[N];
struct Node{
    int l,r;
    ll sum,d;
}tr[N << 2];

ll gcd(ll a,ll b){
    return b?gcd(b,a%b):a;
}

void pushup(Node &u,Node &l,Node &r){
    u.sum = l.sum + r.sum;
    u.d = gcd(l.d,r.d);    
}

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

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

void modify(int u,int x,ll v){
    if(tr[u].l == x && tr[u].r == x){
        ll b = tr[u].sum + v;
        tr[u] = {x,x,b,b};
    }else{
        int 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(int u,int l,int r){
    if(tr[u].l >= l && tr[u].r <= r) return tr[u];
    else{
        int 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(){
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i ++ ) scanf("%lld",&w[i]);
    build(1,1,n);
    int l,r; 
    ll d;
    char op[2];
    while(m -- ){
        scanf("%s%d%d",op,&l,&r);
        if(*op == 'Q'){
            auto left = query(1,1,l),right = query(1,l + 1,r);
            printf("%lld\n",abs(gcd(left.sum,right.d)));    
        }else{
            scanf("%lld",&d);
            modify(1,l,d);
            if(r + 1 <= n) modify(1,r + 1,-d);
        }
    }    
    return 0;
}