线段树维护区间gcd

参考博客

#include<bits/stdc++.h>
using namespace std;
int const N=1e5+7;
#define ll long long
ll tr[N<<2],trs[N<<2],trg[N<<2];  //tr表示差分最大值,trs表示差分和，trg表示差分后的区间gcd
int n,m;
int a[N],b[N];
void pushup(int p){
    //tr[p]=max(abs(tr[p*2]),abs(tr[p*2+1]));
    tr[p]=max(tr[p*2],tr[p*2+1]);
    trs[p]=trs[p*2]+trs[p*2+1];
    trg[p]=__gcd(trg[p*2],trg[p*2+1]);
}
void bulid(int p,int l,int r){
    if(l==r) {
        tr[p]=abs(a[l]);
        trs[p]=trg[p]=a[l];return ;
    }
    int mid=(l+r) >> 1;
    bulid(p*2,l,mid);
    bulid(p*2+1,mid+1,r);
    pushup(p);
}
void add(int p,int l,int r,int x,int k){
    if(l==r){
        if(l==x){
            trs[p]=trg[p]=trs[p]+k;
            tr[p]=abs(trs[p]);
        }
        return ;
    }
    int mid=(l+r) >> 1;
    if(x<=mid) add(p*2,l,mid,x,k);
    else add(p*2+1,mid+1,r,x,k);
    pushup(p);
}
ll ask(int p,int l,int r,int x,int y){
    if(x<=l&&r<=y){
        return tr[p];
    }
    int mid=(l+r) >> 1;
    ll res=0;
    if(x<=mid) res=max(res,ask(p*2,l,mid,x,y));
    if(mid+1<=y) res=max(res,ask(p*2+1,mid+1,r,x,y));
    return res;
}
ll ask2(int p,int l,int r,int x,int y){
    if(x<=l&&r<=y) return trg[p];
    int mid=(l+r) >> 1;
    ll res=0;
    if(x<=mid) res=ask2(p*2,l,mid,x,y);
    if(mid+1<=y) res=__gcd(res,ask2(p*2+1,mid+1,r,x,y));
    return res;
}
ll ask3(int p,int l,int r,int x,int y){
    if(x<=l&&r<=y) return trs[p];
    int mid=(l+r) >> 1;
    ll res=0;
    if(x<=mid) res+=ask3(p*2,l,mid,x,y);
    if(mid+1<=y) res+=ask3(p*2+1,mid+1,r,x,y);
    return res;
}
int main(){
    cin >> n >> m;
    for(int i=1;i<=n;++i){
        cin >> b[i];a[i]=b[i]-b[i-1];   //注意差分的定义
    }
    int op,l,r,x;
    bulid(1,1,n);
    while(m--){
        cin >> op >> l >> r;
        if(op==1){
            cin >> x;
            add(1,1,n,l,x);
            if(r+1<=n) add(1,1,n,r+1,-x);
        }
        else if(op==2){
            if(l==r) cout << 0 << "\n";
            else cout << ask(1,1,n,l+1,r) << "\n";
        }
        else{
            if(l==r) cout << ask3(1,1,n,1,l) << "\n";
            else cout << abs(__gcd( ask3(1,1,n,1,l),ask2(1,1,n,l+1,r)) ) << "\n";
        }
    }
    return 0;
}