Skip to content

P10463 Interval GCD

原题链接：P10463 Interval GCD

Tag：线段树、数学

题目描述

给定一个长度为 \(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 \le 500000\)，\(M \le 100000\)， \(1 \le A[i] \le 10^{18}\)，\(|d| \le 10^{18}\)，保证数据在计算过程中不会超过 long long 范围。

分析

本题很显然需要我们维护一个区间加同时求区间 \(\text{GCD}\)。

首先我们考虑如何求 \(\text{GCD}\)。 我们可以用 \(\gcd(a,b) = \gcd(a,b-a)\)， 尝试把这个式子推广到更多参数的形式， 即 \(\gcd(a,b,c) = \gcd(a,b-a,c-b)\)。

观察可以发现等式右边是一个差分的形式， 所以我们可以对原数组计算出一个差分数组， 可以对这个差分数组维护一个线段树来计算差分数组上的 \(\text{GCD}\)， 这样一来在对区间做加法之后， 在差分数组上的体现是修改了 \(diff_l\) 以及 \(diff_{r+1}\)。 于是我们在执行区间加的时候只需要对差分数组进行两个单点修改就可以了。 即对于 \([L,R]\) 的区间加 \(k\)， 我们只需要让 \(diff_{L}\) 加 \(k\)， 并且让 \(diff_{R+1}\) 减 \(k\)（在 \(R+1\) 不越界的情况下）。 之后对这两个点 \(\text{pushUp}\) 就完成了维护区间 \(\text{GCD}\) 的目标。

但是显然只做到这样是不够的， 我们可以考虑一下我们在这个维护 \(\text{GCD}\) 的线段树上查询出来的是什么， 假设我们查询了一个 \([i,j]\) 的区间， 实际上我们查询出来的东西是 \(\gcd(diff_i-diff_{i-1},diff_{i+1}-diff_i,...,diff_j-diff_{j-1})\)。 但是很显然这个东西并不是我们要的， 我们需要的是 \(\gcd(a_i,diff_{i+1}-diff_i,...,diff_j-diff_{j-1})\)。

因此我们还需要一颗线段树来维护原本的数组， 最后我们查询一个区间 \([L,R]\) 的时候， 我们在差分数组上查询 \([L+1,R]\) 的区间 \(\text{GCD}\)。 之后我们查询原数组上的 \(a_L\)， 将这两个结果放到一起做一个 \(\text{GCD}\) 就得出了答案。

由于我写了两个不一样的线段树结构贴上去了， 所以实现看起来十分长， 读者可以理解做法后自行实现。

代码实现

struct SegmentTreeAdd {
#define lc(a) (a) << 1
#define rc(a) (a) << 1 | 1
    struct TreeNode{
        int l,r,sum,add;
    };
    static const int TreeNodeMax = 5e5+5;
    int val[TreeNodeMax];
    TreeNode tree[TreeNodeMax << 2];
    void build(int cur,int l,int r){
        tree[cur] = {l,r,val[l],0};
        if(l == r) return;
        int mid = (l + r) >> 1;
        build(lc(cur),l,mid);
        build(rc(cur),mid + 1,r);
        pushUp(cur);
    }
    void pushUp(int cur){
        tree[cur].sum = tree[lc(cur)].sum + tree[rc(cur)].sum;
    }
    void pushDown(int cur){
        if(tree[cur].add){
            tree[lc(cur)].sum += tree[cur].add * (tree[lc(cur)].r - tree[lc(cur)].l + 1);
            tree[rc(cur)].sum += tree[cur].add * (tree[rc(cur)].r - tree[rc(cur)].l + 1);
            tree[lc(cur)].add += tree[cur].add;
            tree[rc(cur)].add += tree[cur].add;
            tree[cur].add = 0;
        }
    }
    void update(int cur,int l,int r,int k){
        if(l <= tree[cur].l && tree[cur].r <= r){
            tree[cur].sum += (tree[cur].r - tree[cur].l + 1) * k;
            tree[cur].add += k;
            return;
        }
        int mid = (tree[cur].l + tree[cur].r) >> 1;
        pushDown(cur);
        if(l <= mid) update(lc(cur),l,r,k);
        if(r > mid) update(rc(cur),l,r,k);
        pushUp(cur);
    }
    int query(int cur,int l,int r){
        if(l <= tree[cur].l && tree[cur].r <= r){
            return tree[cur].sum;
        }
        int mid = (tree[cur].l + tree[cur].r) >> 1;
        pushDown(cur);
        int res = 0;
        if(l <= mid) res += query(lc(cur), l, r);
        if(r > mid) res += query(rc(cur), l, r);
        return res;
    }
};
struct SegmentTreeGCD {
#define lc(a) (a) << 1
#define rc(a) (a) << 1 | 1
    struct TreeNode{
        int l,r,gcd;
    };
    static const int TreeNodeMax = 5e5+5;
    int val[TreeNodeMax];
    TreeNode tree[TreeNodeMax << 2];
    void build(int cur,int l,int r){
        tree[cur] = {l,r,val[l]};
        if(l == r) return;
        int mid = (l + r) >> 1;
        build(lc(cur),l,mid);
        build(rc(cur),mid + 1,r);
        pushUp(cur);
    }
    void pushUp(int cur){
        tree[cur].gcd = gcd(tree[lc(cur)].gcd,tree[rc(cur)].gcd);
    }
    void update(int cur,int l,int r,int k){
        if(tree[cur].l == l && tree[cur].r == r){
            tree[cur].gcd += k;
            return;
        }
        int mid = (tree[cur].l + tree[cur].r) >> 1;
        if(l <= mid) update(lc(cur),l,r,k);
        if(r > mid) update(rc(cur),l,r,k);
        pushUp(cur);
    }
    int query(int cur,int l,int r){
        if(l <= tree[cur].l && tree[cur].r <= r){
            return tree[cur].gcd;
        }
        int mid = (tree[cur].l + tree[cur].r) >> 1;
        int res = 0;
        if(l <= mid) res = gcd(res,query(lc(cur), l, r));
        if(r > mid) res = gcd(res,query(rc(cur), l, r));
        return res;
    }
};
SegmentTreeAdd addSeg;
SegmentTreeGCD gcdSeg;
void NeverSayNever() {
    int n, q; cin >> n >> q;
    vector<int> vec(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> vec[i];
        addSeg.val[i] = vec[i];
    }
    addSeg.build(1, 1, n);
    vector<int> diff(n + 1);
    for (int i = 1; i <= n; ++i) {
        diff[i] = vec[i] - vec[i - 1];
        gcdSeg.val[i] = diff[i];
    }
    gcdSeg.build(1, 1, n);
    while (q--) {
        char op; cin >> op;
        if (op == 'C') {
            int l, r, d; cin >> l >> r >> d;
            addSeg.update(1, l, r, d);
            gcdSeg.update(1, l, l, d);
            if (r + 1 <= n)
                gcdSeg.update(1, r + 1, r + 1, d * (-1));
        } else {
            int l, r; cin >> l >> r;
            int ans1 = addSeg.query(1, l, l);
            int ans2 = gcdSeg.query(1, l + 1, r);
            cout << gcd(ans1, ans2) << endl;
        }
    }
}

日志

本页面创建于 2024/8/2 23:07

特别鸣谢：

gongkoufadongji的细心指导