【线段树】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行每条指令的格式如题目描述所示。

输出

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

样例输入

5 5

1 3 5 7 9

Q 1 5

C 1 5 1

Q 1 5

C 3 3 6

Q 2 4

样例输出

1

2

4

提示

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)……对任意多个整数都成立然后用线段树维护这个差分序列，更新gcd。再用树状数组来维护原序列x的值。细节注意

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define L(u) (u<<1)

#define R(u) (u<<1|1)

const int maxn=5e5+10;

ll c[maxn];

int n,m;

template<class T>

void read(T &res) {

    res = 0;

    char c = getchar();

    T f = 1;

    while(c < '0' || c > '9')

    {

        if(c == '-') f = -1;

        c = getchar();

    }

    while(c >= '0' && c <= '9')

    {

        res = res * 10 + c - '0';

        c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) {

        putchar('-');

        x = -x;

    }

    if(x >= 10)

    {

        out(x / 10);

    }

    putchar('0' + x % 10);

}

struct Node{

    int l,r;

    ll val;

}node[maxn<<2];

int lowbit(int x)

{

    return x&-x;

}

void add(int x,ll val)

{

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

        c[i]+=val;

}

ll get_sum(int x)

{

    ll ret=0;

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

        ret+=c[i];

    return ret;

}

ll s[maxn],a[maxn];

void push_up(int u){//

    node[u].val=__gcd(node[L(u)].val,node[R(u)].val);

}

void build(int u,int l,int r){

    node[u].l=l,node[u].r=r;

    if(l==r){

        node[u].val=s[l];

        return;

    }

        int mid=(l+r)>>1;

        build(L(u),l,mid);

        build(R(u),mid+1,r);

        push_up(u);

}

ll query(int u,int l,int r){

    if(l<=node[u].l&&node[u].r<=r){

        return node[u].val;

    }

        int mid=(node[u].l+node[u].r)>>1;

        if(r<=mid) return query(L(u),l,r);

        else if(l>mid) return query(R(u),l,r);

        else return __gcd(query(L(u),l,mid),query(R(u),mid+1,r));

}

void update(int u,int x,ll val){

    if(node[u].l==node[u].r){

        node[u].val+=val;

        return;

    }

    int mid=(node[u].l+node[u].r)>>1;

    if(x<=mid) update(L(u),x,val);

    else update(R(u),x,val);

    push_up(u);

}

int main(){

   read(n);

   read(m);

    for (int i = 1; i <=n ; ++i) {

       read(a[i]);

       s[i]=a[i]-a[i-1];

       add(i,s[i]);

    }

    char str;int l,r;

    ll d;

    build(1,1,n);

    for(int i=1;i<=m;++i) {

        scanf(" %c", &str);

        if (str == 'C') {

            read(l);

            read(r);

            read(d);

            add(l, d);

            add(r + 1, -d);

            update(1, l, d);

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

        } else {

            read(l);read(r);

            ll ans = abs(__gcd(get_sum(l), query(1, l+1, r)));

            out(ans);

            puts("");

        }

    }

}

巴特西

【线段树】Interval GCD

题目描述

输入

输出

样例输入

样例输出

提示

题解

最新文章

热门文章