题解：P10463 Interval GCD

tangml · 2024-06-27 21:34:56 · 题解

线段树板子题

我们知道更相减损术求最大公约数的方法，实际上，该结论可进一步扩展至三个数乃至多个数的情况下，可以用数学归纳法证明。

所以，我们可以构造一个长度为 N 的新数列，做 A 的差分数列，用线段树维护新数列的区间最大公约数。

#include<bits/stdc++.h>

using namespace std;

const int M=500100;

int n,m;
long long w[M];

struct SegmentTree
{
    int l,r;
    long long sum,d;
}t[M*4];

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

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

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

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

void change(int u,int x,long long v)
{
    if(t[u].l==x&&t[u].r==x)
    {
        long long b=t[u].sum+v;
        t[u]={x,x,b,b};
    }
    else
    {
        int mid=(t[u].l+t[u].r)>>1;
        if(x<=mid) change(u<<1,x,v);
        else       change(u<<1|1,x,v);
        pushup(u);
    }
}

SegmentTree ask(int u,int l,int r)
{
    if(t[u].l>=l&&t[u].r<=r) return t[u];
    else
    {
        int mid=(t[u].l+t[u].r)>>1;
        if(r<=mid) return ask(u<<1,l,r);
        else if(l>mid) return ask(u<<1|1,l,r);
        else
        {
            SegmentTree left=ask(u<<1,l,r);
            SegmentTree right=ask(u<<1|1,l,r);
            SegmentTree res;
            pushup(res,left,right);
            return res;
        }
    }
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) scanf("%lld",&w[i]);
    build(1,1,n);

    int l,r;
    long long d;
    char op[2];
    while(m--)
    {
        scanf("%s%d%d",op,&l,&r);
        if(*op=='Q')
        {
            SegmentTree left=ask(1,1,l),right=ask(1,l+1,r);
            printf("%lld\n",abs(gcd(left.sum,right.d)));
        }
        else
        {
            scanf("%lld",&d);
            change(1,l,d);
            if(r+1<=n) change(1,r+1,-d);
        }
    }

    return 0;
}