题解：P12579 [UOI 2021] 哥萨克与 GCD

Invisible_H · 2025-05-22 16:32:53 · 题解

Part 1

前置知识：最小生成树。

先进行一个转化：

每次花费 \gcd_{i=l + 1}^{r} B_i 的代价，可以连 (l,r) 这一条边。

然后我们需要求 0∼n 的最小生成树。

代码很好写啊就建完全图跑最小生成树，记得清空 fa 数组，时间复杂度 O(q n ^2 \log n)。

#include <bits/stdc++.h>
#define int long long

constexpr int maxn = 1e6 + 7;
int B[maxn];
struct node{
    int u, v, w;
}G[maxn];
int fa[maxn], n, q;
inline int find(int u){
    if(u != fa[u]){
        fa[u] = find(fa[u]);
    }
    return fa[u];
}
inline bool cmp(node a, node b){
    return a.w < b.w; 
}
int32_t main(){
    std::cin.tie(nullptr) -> std::ios::sync_with_stdio(false);
    std::cin >> n >> q;
    for(int i = 1; i <= n; i++){
        std::cin >> B[i];
    }
    for(int i = 0; i <= n; i++){
        fa[i] = i;
    }
    int m = 0;
    int k, val;
    for(int i = 0; i <= n; i++){
        int g = B[i + 1];
        for(int j = i + 1; j <= n; j++){
            g = std::__gcd(g, B[j]);
            G[++m].u = i;
            G[m].v = j;
            G[m].w = g;

        }
    }
    int ans = 0;
    std::sort(G + 1, G + m + 1, cmp);
    int cnt = 0;
    for(int i = 1; i <= m; i++){
        int fu = find(G[i].u), fv = find(G[i].v);
        if(fu == fv) continue;
        ans += G[i].w;
        fa[fv] = fu;
        cnt++;
        if(cnt == n) break;
    }
    std::cout << ans << '\n';
    while(q--){
        for(int i = 0; i <= n; i++){
            fa[i] = i;
        }
        int m = 0;
        int k, val;
        std::cin >> k >> val;
        B[k] = val;
        for(int i = 0; i <= n; i++){
            int g = B[i + 1];
            for(int j = i + 1; j <= n; j++){
                g = std::__gcd(g, B[j]);
                G[++m].u = i;
                G[m].v = j;
                G[m].w = g;

            }
        }
        int ans = 0;
        std::sort(G + 1, G + m + 1, cmp);
        int cnt = 0;
        for(int i = 1; i <= m; i++){
            int fu = find(G[i].u), fv = find(G[i].v);
            if(fu == fv) continue;
            ans += G[i].w;
            fa[fv] = fu;
            cnt++;
            if(cnt == n) break;
        }
        std::cout << ans << '\n';
    }
    return 0;
}

Part 2

考虑优化。

前置知识：最小生成树。

根据 Kruskal 的思想，(0,n) 这条边一定会被选。

然后根据 Prim 的思想，对于某个点，我们需要找到其最短的出边。

而显然对于 i，它最短的出边为 (i,0) 或者 (i,n)。边权为 L_i=\gcd_{j=1}^{i} B_j 和 R_i=\gcd_{j=i+1}^{n} B_j。

然后你只需要建 0 到所有点的边和 n 到所有点的边就好了，时间复杂度 O(q n \log n)。

#include <bits/stdc++.h>
#define int long long

constexpr int maxn = 1e6 + 7;
int B[maxn], m;
struct node{
    int u, v, w;
}G[maxn];
int fa[maxn], n, q;
inline int find(int u){
    if(u != fa[u]){
        fa[u] = find(fa[u]);
    }
    return fa[u];
}
inline bool cmp(node a, node b){
    return a.w < b.w; 
}
int32_t main(){
    std::cin.tie(nullptr) -> std::ios::sync_with_stdio(false);
    std::cin >> n >> q;
    for(int i = 1; i <= n; i++){
        std::cin >> B[i];
    }
    for(int i = 0; i <= n; i++){
        fa[i] = i;
    }
    int m = 0;
    int k, val;
    int g = 0;
    for(int i = 1; i <= n; i++){
        g = std::__gcd(g ,B[i]);
        G[++m].u = 0;
        G[m].v = i;
        G[m].w = g;
    }
    g = 0;
    for(int i = n; i >= 1; i--){
        g = std::__gcd(g ,B[i]);
        G[++m].u = i - 1;
        G[m].v = n;
        G[m].w = g;
    }
    int ans = 0;
    std::sort(G + 1, G + m + 1, cmp);
    int cnt = 0;
    for(int i = 1; i <= m; i++){
        int fu = find(G[i].u), fv = find(G[i].v);
        if(fu == fv) continue;
        ans += G[i].w;
        fa[fv] = fu;
        cnt++;
        if(cnt == n) break;
    }
    std::cout << ans << '\n';
    while(q--){
        for(int i = 0; i <= n; i++){
            fa[i] = i;
        }
        int m = 0;
        int k, val;
        std::cin >> k >> val;
        B[k] = val;
        int g = 0;
        for(int i = 1; i <= n; i++){
            g = std::__gcd(g ,B[i]);
            G[++m].u = 0;
            G[m].v = i;
            G[m].w = g;
        }
        g = 0;
        for(int i = n; i >= 1; i--){
            g = std::__gcd(g ,B[i]);
            G[++m].u = i - 1;
            G[m].v = n;
            G[m].w = g;
        }
        int ans = 0;
        std::sort(G + 1, G + m + 1, cmp);
        int cnt = 0;
        for(int i = 1; i <= m; i++){
            int fu = find(G[i].u), fv = find(G[i].v);
            if(fu == fv) continue;
            ans += G[i].w;
            fa[fv] = fu;
            cnt++;
            if(cnt == n) break;
        }
        std::cout << ans << '\n';
    }
    return 0;
}

Part 3

考虑继续优化。

前置知识：线段树二分。

显然 L_i 是单调不增，R_i 是单调不减的。

所以一定存在一个 p \in [0,n),\forall i\in[0,p],R_i \leq Li,\forall i \in (p,n),Li \leq Ri。

我们可以用线段树维护每个区间 [l,r] 的 \gcd_{l+1}^{r} B_i，然后在线段树上二分求出 p。

而题目所给的修改可以直接单点修改。

剩下的就是求 \sum_{i=0}^{p} R_i + \sum_{i=p+1}^{n-1} L_i。

考虑到 L_i 以及 R_i 的取值个数是 \log n 级别的，我们可以在线段树上暴力找出这些取值以及其对应的区间，时间复杂度 O(q \log^2 n)。

#include <bits/stdc++.h>
#define mid ((l+r)>>1)
#define int long long
int SGT[400007];
void build(int p, int l, int r) {
    if (l == r)
        return (void)(std::cin >> SGT[p]);

    build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r), SGT[p] = std::__gcd(SGT[p << 1], SGT[p << 1 | 1]);
}
void update(int p, int l, int r, int x, int v) {
    if (l == r)
        return (void)(SGT[p] = v);

    x <= mid ? update(p << 1, l, mid, x, v) : update(p << 1 | 1, mid + 1, r, x, v);
    SGT[p] = std::__gcd(SGT[p << 1], SGT[p << 1 | 1]);
}
int Find(int p, int l, int r, int a, int b) {
    if (l == r)
        return l;

    int x = std::__gcd(a, SGT[p << 1]), y = std::__gcd(b, SGT[p << 1 | 1]);
    return x <= y ? Find(p << 1, l, mid, a, y) : Find(p << 1 | 1, mid + 1, r, x, b);
}
int cal1(int p, int l, int r, int x, int v) {
    if (l == r)
        return std::__gcd(SGT[p], v);

    int a = std::__gcd(SGT[p << 1 | 1], v), b = std::__gcd(SGT[p << 1], a);
    return x <= mid ? cal1(p << 1, l, mid, x, a) : (a == b ? 1ll * (mid - l + 1) * a : cal1(p << 1, l, mid, x, a)) + cal1(p << 1 | 1, mid + 1, r, x, v);
}
int cal2(int p, int l, int r, int x, int v) {
    if (l == r)
        return std::__gcd(SGT[p], v);

    int a = std::__gcd(SGT[p << 1], v), b = std::__gcd(SGT[p << 1 | 1], a);
    return x > mid ? cal2(p << 1 | 1, mid + 1, r, x, a) : (a == b ? 1ll * (r - mid) * a : cal2(p << 1 | 1, mid + 1, r, x, a)) + cal2(p << 1, l, mid, x, v);
}
int32_t main() {
    int n, Q;
    std::cin >> n >> Q; 
    build(1, 1, n);
    int p = Find(1, 1, n, 0, 0);
    std::cout << (cal1(1, 1, n, p, 0) + cal2(1, 1, n, p, 0) - SGT[1]) << '\n';
    for (int p, v; Q; --Q) std::cin >> p >> v, update(1, 1, n, p, v), p = Find(1, 1, n, 0, 0), std::cout << (cal1(1, 1, n, p, 0) + cal2(1, 1, n, p, 0) - SGT[1]) << '\n';

    return 0;
}