AcWing 246. 区间最大公约数

2024-01-09 20:30:10

传送门

题目描述

给定一个长度为N的数列A，以及M条指令，每条指令可能是以下两种之一：

1、“C l r d”，表示把 A[l],A[l+1],…,A[r] 都加上 d。

2、“Q l r”，表示询问 A[l],A[l+1],…,A[r] 的最大公约数(GCD)。

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

输入格式

第一行两个整数N,M。

第二行N个整数A[i]。

接下来M行表示M条指令，每条指令的格式如题目描述所示。

输出格式

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

每个答案占一行。

数据范围

N≤500000,M≤100000

输入样例：

输出样例：

1
2
4

题解：线段树用于在区间上进行信息统计，这题求区间GCD显然可以用线段树来做。同时题目还需要区间更新。

　　　我们知道gcd(x,y) = gxd (x,y-x)。它可以进一步扩展到三个数的情况：gcd(x,y,z) = gcd(x,y-x,z-y)。因此我们可以构造一个长度为N的新数列B，其中B[i] = A[i] - A][i-1]。数列B为A的差分序列。用线段树维护序列B的区间GCD就相当于维护A的区间GCD。这样一来询问[l,r]的GCD就相当于求gcd(A[l],B[l+1,r]的gcd)，更新[l,r]只需在B的线段树上更新l和r+1这两个点即可（注意r+1<=n），同时还要修改A中的值，这时我们可以用支持“区间修改、单点查询”的树状数组来维护。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 5e5 + 10;
struct node{
    ll l,r,gcd;
}T[N<<2];
ll a[N],b[N],c[N];
void up(int rt) {
    T[rt].gcd = __gcd(T[rt<<1].gcd,T[rt<<1|1].gcd);
}
void build(int rt,ll l,ll r) {
    T[rt].l = l,T[rt].r = r;
    if (l == r) {
        T[rt].gcd = b[l];
        return;
    }
    ll mid = (l+r)>>1;
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
    up(rt);
}
void update(int rt,ll x,ll val) {
    if (T[rt].l == T[rt].r && T[rt].l == x) {
        T[rt].gcd += val;
        return;
    }
    ll mid = (T[rt].l + T[rt].r)>>1;
    if (x <= mid) update(rt<<1,x,val);
    else update(rt<<1|1,x,val);
    up(rt);
}
ll ask(int rt,ll l,ll r){
    if (l <= T[rt].l && r >= T[rt].r) return abs(T[rt].gcd);
    ll mid = (T[rt].l+T[rt].r)>>1;
    ll ans1 = 0,ans2 = 0;
    if (l<=mid) ans1 = ask(rt<<1,l,r);
    if (r>mid) ans2 = ask(rt<<1|1,l,r);
    return abs(__gcd(ans1,ans2));
}
ll lowbit(ll x) { return x&(-x); }
void add(ll x,ll val) {
    for (;x<N;x+=lowbit(x)) c[x]+=val;
}
ll query(ll x) {
    ll ans = 0;
    for (;x>0;x-=lowbit(x)) ans += c[x];
    return ans;
}
int main() {
    int n,m;
    scanf("%d%d",&n,&m);
    for (int i = 1; i <= n; i++) {
        scanf("%lld",&a[i]);
        b[i] = a[i] - a[i-1];
    }
    build(1,1,n);
    while (m--) {
        char op[5];
        ll l,r,x;
        scanf("%s%lld%lld",op,&l,&r);
        if (op[0] == 'Q') printf("%lld\n",__gcd(a[l]+query(l),ask(1,l+1,r)));
        else {
            scanf("%lld",&x);
            update(1,l,x);
            if (r<n) update(1,r+1,-x);
            add(l,x);
            add(r+1,-x);
        }
    }
    return 0;
}

View Code

码农公寓