gcd查询

gcd查询

给定一个序列 有三种操作:

1. :在区间 加上 .

2. : 查询区间 中的 .

3. :查询 .

根据 的性质, ,设 是 的差分数组,对于任意一个区间
由于 的性质,在区间 加上一个数
其实只对 有用所以只需要维护 数组就可以单点更新即可,求询问2刚好在差分数组上单点更新就可以.

#include<bits/stdc++.h>
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define itn int
using namespace std;
const int N=1e6;
const long long mod=1e9+7;
const int oo=0x7fffffff;
const int sup=0x80000000;
typedef long long ll;
typedef unsigned long long ull;
template <typename it>void db(it *begin,it *end){while(begin!=end)cout<<(*begin++)<<" ";puts("");}
template <typename it>
string to_str(it n){string s="";while(n)s+=n%10+'0',n/=10;reverse(s.begin(),s.end());return s;}
template <typename it>int o(it a){cout<<a<<endl;return 0;}
ll mul(ll a,ll b,ll c){ll ans=0;for(;b;b>>=1,a=(a+a)%c)if(b&1)ans=(ans+a)%c;return ans;}
ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=mul(a,a,c))if(b&1)ans=mul(ans,a,c);return ans;}
int n,m;
int MAX[N],MIN[N],gcd[N];
int pos[N],sum[N]={0};
int main(){
    //freopen("in.txt","r",stdin);
    cin>>n>>m;
    vector<int>cdi(n+5,0),cnt(n+5,0);
    function<void(int x,int val)>modify=[&](int x,int val){for(int i=x;i<=n;i+=i&(-i))sum[i]+=val;};
    function<int(int x)>getsum=[&](int x){int res=0;for(int i=x;i;i&=i-1)res+=sum[i];return res;};
    for(int i=1;i<=n;i++){
        sc("%d",&cdi[i]);
        if(i==1)cnt[i]=cdi[i];
        else cnt[i]=cdi[i]-cdi[i-1];
        modify(i,cnt[i]);
    }
    function<void(int rt)>push=[&](int rt){
        gcd[rt]=__gcd(gcd[rt<<1],gcd[rt<<1|1]);
        MAX[rt]=max(MAX[rt<<1],MAX[rt<<1|1]);
        MIN[rt]=min(MIN[rt<<1],MIN[rt<<1|1]);
    };
    function<void(int l,int r,int rt)>
    tree=[&](int l,itn r,int rt){
        if(l==r){
            pos[l]=rt;
            gcd[rt]=cnt[l];
            MAX[rt]=MIN[rt]=cnt[l];
            return;
        }
        int mid=l+r>>1;
        tree(l,mid,rt<<1);
        tree(mid+1,r,rt<<1|1);
        push(rt);
    };
    function<void(int pt,int val)>
    up=[&](int pt,int val){
        int x=pos[pt];
        gcd[x]+=val;
        MIN[x]=(MAX[x]+=val);
        while(x>1)x>>=1,push(x);
    };
    function<int(int l,int r,itn rt,int L,int R,int op)>
    Q=[&](int l,itn r,int rt,int L,int R,int op){
        if(l>=L&&r<=R){
            if(op==1)return MAX[rt];
            if(op==2)return MIN[rt];
            if(op==3)return gcd[rt];
        }
        int mid=l+r>>1;
        if(op==1){
            int x=sup;
            if(mid>=L)x=max(x,Q(l,mid,rt<<1,L,R,op));
            if(mid<R)x=max(x,Q(mid+1,r,rt<<1|1,L,R,op));
            return x;
        }else if(op==2){
            int x=oo;
            if(mid>=L)x=min(x,Q(l,mid,rt<<1,L,R,op));
            if(mid<R)x=min(x,Q(mid+1,r,rt<<1|1,L,R,op));
            return x;
        }else{
            int x=0;
            if(mid>=L)x=__gcd(x,Q(l,mid,rt<<1,L,R,op));
            if(mid<R)x=__gcd(x,Q(mid+1,r,rt<<1|1,L,R,op));
            return x;
        }
    };
    tree(1,n,1);
    while(m--){
        int op; sc("%d",&op);
        if(op==1){
            int l,r,x;
            sc("%d%d%d",&l,&r,&x);
            modify(l,x);modify(r+1,-x);
            up(l,x);up(r+1,-x);
        }else if(op==2){
            int l,r;
            sc("%d%d",&l,&r);
            if(l==r){
                puts("0");
                continue;
            }
            int mi=Q(1,n,1,l+1,r,2);
            int ma=Q(1,n,1,l+1,r,1);
            printf("%d\n",max(abs(mi),abs(ma)));
        }else{
            int l,r;
            sc("%d%d",&l,&r);
            if(l==r){
                printf("%d\n",getsum(l));
                continue;
            }
            int ans=__gcd(getsum(l),Q(1,n,1,l+1,r,3));
            if(ans<0)ans=-ans;
            printf("%d\n",ans);
        }
    }
}