Interval GCD

题目描述

给定一个长度为N的数列A，以及M条指令 (N≤5*10^5, M<=10^5)，每条指令可能是以下两种之一：
“C l r d”，表示把 A[l],A[l+1],…,A[r] 都加上 d。
“Q l r”，表示询问 A[l],A[l+1],…,A[r] 的最大公约数(GCD)。

输入

第一行两个整数N,M，第二行N个整数Ai，接下来M行每条指令的格式如题目描述所示。

输出

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

样例输入

样例输出

提示

N,M≤2*10^5，l<=r，数据保证任何时刻序列中的数都是不超过2^62-1的正整数。

gcd(x,y)=gcd(x,y-x),gcd(x,y,z)=gcd(x,y-x,z-y)……对任意多个整数都成立

将A数列进行查分，线段树维护差分序列的最大公约数，每次询问就是gcd(A[l],query(,,n,l+,r);

每次修改update(1,1,n,l,d),update(1,1,n,r+1,-d)

A数组也需要维护，线段树和树状数组都行

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int N=5e5+;

ll A[N*],a[N],B[N*],b[N];

int n,m;

char op;

int lowbit(int x)

{

    return x&-x;

}

void add(int x,ll val)

{

    for (int i=x;i<=n;i+=lowbit(i))

    A[i]+=val;

}

ll sum(int x)

{

    ll ret=;

    for (int i=x;i>=;i-=lowbit(i))

        ret+=A[i];

    return ret;

}

void Pushup(int s)

{

    B[s]=__gcd(B[s<<],B[s<<|]);

}

void build(int s,int l,int r)

{

    if (l==r)

    {

        B[s]=b[l];

        return ;

    }

    int mid=(l+r)>>;

    build(s<<,l,mid);

    build(s<<|,mid+,r);

    Pushup(s);

}

void update(int s,int l,int r,int pos,ll val)

{

    if (l==r)

    {

        B[s]+=val;

        return ;

    }

    int mid=(l+r)>>;

    if (pos<=mid) update(s<<,l,mid,pos,val);

    else update(s<<|,mid+,r,pos,val);

    Pushup(s);

}

ll query(int s,int l,int r,int L,int R)

{

   // cout<<s<<' '<<l<<' '<<r<<' '<<L<<' '<<R<<' '<<B[s]<<endl;

    if (L<=l&&r<=R) return B[s];

    int mid=(l+r)>>;

    if (R<=mid) return query(s<<,l,mid,L,R);

    else if (L>mid) return query(s<<|,mid+,r,L,R);

    else return __gcd(query(s<<,l,mid,L,R),query(s<<|,mid+,r,L,R));

}

int main()

{

    scanf("%d%d",&n,&m);

    for (int i=;i<=n;i++) scanf("%lld",&a[i]);

    for (int i=;i<=n;i++) b[i]=a[i]-a[i-],add(i,b[i]);

    build(,,n);

    int l,r; ll d;

    while (m--)

    {

        scanf(" %c",&op);

        if (op=='C')

        {

            scanf("%d%d%lld",&l,&r,&d);

            add(l,d);

            add(r+,-d);

            update(,,n,l,d);

            if (r+<=n) update(,,n,r+,-d);

        }

        else

        {

            scanf("%d%d",&l,&r);

            //cout<<sum(l)<<endl;

            //cout<<query(1,1,n,r,r)<<endl;

            //cout<<query(1,1,n,l+1,r)<<endl;

            ll ans=abs(__gcd(sum(l),query(,,n,l+,r)));

            printf("%lld\n",ans);

        }

    }

    return ;

}

巴特西

Interval GCD

题目描述

输入

输出

样例输入

样例输出

提示

最新文章

热门文章