区间最大公约数

AcWing

题意:维护两种操作,区间增加和查询区间最大公约数.

分析:借助于求最大公约数的方法之一:更相减损术,\(gcd(a,b)=gcd(a,b-a)\),推广到任意个都成立,所以可以维护原数组\(A\)的差分数组\(B\),用线段树维护这个差分数组的最大公约数.

对于一个区间增加操作,就只要让\(B[l]+=val,B[r-1]-=val\).即单点修改操作.

对于一次查询,就等于求出\(gcd(A[l],query(1,l+1,r))\).发现我们还要维护\(A\)数组的值,这个可以简单用一个树状数组来维护.

本题细节较多,\(long\) \(long\)是最基本的,然后\(gcd\)如果是负数要变成正数,如果修改操作中的\(r+1>n\)就跳过.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=500005;
ll n,m,a[N],b[N],c[N];
struct XD_Tree{ll l,r,data;}t[N<<2];
inline ll gcd(ll a,ll b){
    if(!b)return a;
    return gcd(b,a%b);
}
inline void build(int p,ll l,ll r){
    t[p].l=l;t[p].r=r;
    if(l==r){t[p].data=b[l];return;}
    ll mid=(l+r)>>1;
    build(p<<1,l,mid);build(p<<1|1,mid+1,r);
    t[p].data=gcd(t[p<<1].data,t[p<<1|1].data);
}
inline void change(int p,ll pos,ll v){
    int l=t[p].l,r=t[p].r;
    if(l==r){t[p].data+=v;return;}
    int mid=(l+r)>>1;
    if(pos<=mid)change(p<<1,pos,v);
    else change(p<<1|1,pos,v);
    t[p].data=gcd(t[p<<1].data,t[p<<1|1].data);
}
inline ll query(int p,ll ql,ll qr){
    int l=t[p].l,r=t[p].r;
    if(ql<=l&&qr>=r)return abs(t[p].data);  
    ll mid=(l+r)>>1,gcdl=0,gcdr=0;
    if(ql<=mid)gcdl=query(p<<1,ql,qr);  
    if(qr>mid)gcdr=query(p<<1|1,ql,qr);
    return abs(gcd(gcdl,gcdr));
}
inline ll lowbit(ll x){return x&-x;}
inline void add(ll x,ll y){for(;x<=n;x+=lowbit(x))c[x]+=y;}
inline ll ask(ll x){ll cnt=0;for(;x;x-=lowbit(x))cnt+=c[x];return cnt;}
int main(){
    n=read();m=read();for(int i=1;i<=n;++i)a[i]=read();
    for(int i=1;i<=n;++i)b[i]=a[i]-a[i-1];build(1,1,n);
    while(m--){
        char ch;cin>>ch;
        if(ch=='C'){
            ll l,r,val;l=read();r=read();val=read();
            add(l,val);if(r+1<=n)add(r+1,-val);
            change(1,l,val);if(r+1<=n)change(1,r+1,-val);
        }
        else if(ch=='Q'){
            ll l,r;l=read();r=read();
            printf("%lld\n",gcd(a[l]+ask(l),query(1,l+1,r)));
        }
    }
    return 0;
}