题解：P13342 [EGOI 2025] Wind Turbines / 风力涡轮机

liangjindong0504 · 2025-08-20 21:44:16 · 题解

前言

使用回滚莫队通过了这一道题，感谢 yingkeqian9217 的点拨。同时以较大的优势抢下最劣解。

疯狂的提交记录

::::warning[警告] 本人实现比较抽象，代码又臭又长，请谨慎阅读。 ::::

Part 1

首先，这个题面好抽象啊，考虑把它转化一下。

不难发现，答案其实就是原图中将 l \sim r 这一段的点缩成一个点，然后求整张图的 MST（最小生成树）中边的权值和。于是我们考虑先将整个图的 MST 求出来。

Part 2

考虑每次询问中 r_i = l_i + 1，即 Subtask 3。将两个点缩成一个点之后，显然相当于在两点之间加一条权值为 0 的边，然后继续求 MST。于是显然，这部分的答案就是 s - w_{max}，s 是原图 MST 的权值，w_{max} 是 l 到 r 最小生成树的路径上权值最大值。

然后你可以获得 13 分。注意到我的代码中把点的编号都加了 1，个人习惯。

Part 3

接下来我们引入 kruskal 重构树。

所谓 kruskal 重构树，就是先按建 MST 的过程，按照边权从小到大排序。然后，当两点在并查集中祖先不是相同的，就考虑将它们合并，同时新开一个点，这两点的祖先为该点的儿子。

同时，我们将这个新开的点的点权设为这条边的权值。

接着，我们会发现一些有趣的事情。

在草稿纸上画出样例的 kruskal 重构树，然后在询问中可以发现，其实用一个 flag 数组，每次询问的时候给两两之间在 kruskal 重构树上的 LCA 打上 tag，最后用 MST 的权值减去这些被标记的点的权值即可。

对于这一点我也是感性理解的，个人的感觉是考虑 kruskal 过程，两个点只能在合并处节约。也就是一开始先是两点之间被连了一条权值为 0 的边，那么原先 合并的地方就不用合并了。只有 11 分。

两份代码合并起来就以后 24pts 了！！！

实际上用莫队乱搞一下也可以获得 24 分。提交记录。

Part 4

接下来的这个做法可以获得 54 分。

我们还是考虑莫队。之前的莫队之所以慢，显然是因为每次插入或者删除的时候都要把其他的都扫一遍。这显然是很慢的。那么我们考虑，能不能对于添加、删除做到更优的复杂度？

首先我们需要做到 O(1) 求 LCA 。预处理 O(n\log n)。

发现，两个点之间的 LCA 只跟它们的 dfs 序（dfn）有关。为何？我们发现，设两个点为 u,v 且 dfn_u < dfn_v，它们的 LCA 为 t，那么显然，t 到 v 的这段路径（除去 t）上的所有点的 dfs 序都在 dfn_u 到 dfn_v 之间。

那么显然，两点的 LCA 就是所有 x，满足 dfn_u \le dfn_x \le dfn_v 中 dep 最小的节点的父亲。dep_x 表示 x 的深度。

接下来我们说明，扩展或者删除的时候，被标记的点的数量只会变化 1。这点可以从 Part 1 中得到。因为扩展的时候，相当于边权为 0 的边又多了一条，可以少打一个 tag。删除同理，即多打一个 tag。

不难发现，加入一个点的时候，我们寻找的是它和其他已经处理过的点中所有 LCA 深度最大的点。原因很简单，因为如果不是深度最大的点，那么一定是这个点的祖先，并且一定之前已经打过 tag 了。

换一种角度理解，也就是说，对于找到的那个点的祖先，与被加入点同侧的一定有另一个叶子，于是这个点要么不是新加点与原有点的 LCA，要么已经被打过 tag 了。

随后，我们考虑使用 set 维护 dfn 序，每次插入删除可以 O(\log n) 完成。于是，我们可以 O(n \sqrt n \log n) 解决。期望得分 54 分，下面是代码。卡卡就过了。

::::info[54 分代码]

#include <bits/stdc++.h>

using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;

const int MAXN = 2e5 + 10;
const int INF  = 1e9;

struct node {
    int x;
    i64 val;

    bool operator < (const node &tmp) const {
        return x < tmp.x;
    }
};

struct DSU {
    int n;
    std::vector <int> fa;
    DSU (int n_) : n(n_), fa(n + 10) {};

    void init() {
        for (int i = 1; i <= n; ++i) {
            fa[i] = i;
        }
    }

    int find (int x) {
        return fa[x] == x ? x : fa[x] = find(fa[x]);
    }
};

struct EDGE {
    int u, v;
    i64 w;

    bool operator < (const EDGE &tmp) const {
        return w < tmp.w;
    }
};

struct EDGE2 {
    int to, w;
};

int B;

struct QUESTION {
    int l, r, id;
    i64 ans;

    bool operator < (const QUESTION &tmp) const {
        int nl = (l + B - 1) / B;
        int pl = (tmp.l + B - 1) / B;
        if (nl == pl) {
            if (nl % 2) {
                return r < tmp.r;
            } else {
                return tmp.r < r;
            }
        }
        return nl < pl;
    }
};

bool cmp (QUESTION x, QUESTION y) {
    return x.id < y.id;
}

int n, m, q;
int dep[MAXN];
int dfn[MAXN];
int st[MAXN][20];
int stid[MAXN][20];

int tot;
int tot1;

int fa[MAXN];

i64 val[MAXN];
i64 tag[MAXN];

i64 s, ans;

EDGE e[MAXN];
QUESTION ask[MAXN];

std::vector <int> edge;
std::vector <int> mst[MAXN];
std::vector <node> pos[MAXN];

void dfs (int x, int lst) {
    dfn[x] = ++tot1;
    fa[dfn[x]] = lst;
    dep[x] = dep[lst] + 1;
    st[dfn[x]][0] = st[dfn[lst]][0] + 1;
    stid[dfn[x]][0] = dfn[x];

    for (auto to : mst[x]) {
        if (to == lst) {
            continue;
        }

        dfs(to, x);
    }
}

int lg[MAXN];
int o[MAXN];

std::set <int> f;

node rmq (int l, int r) {
    if (l > r) std::swap(l, r);
    int k = lg[r - l + 1];
    int k1 = st[l][k], k2 = st[r - (1 << k) + 1][k];
    if (k1 < k2) {
        return (node){stid[l][k], k1};
    } else {
        return (node){stid[r - (1 << k) + 1][k], k2};
    }
}

void add (int x) {
    if (!f.size()) {
        f.insert(dfn[x]);
        return;
    }

    int maxn = 0;
    int p;

    auto cur = f.insert(dfn[x]).first;
    auto suf = cur;
    auto pre = suf;
    ++suf;
    if (pre != f.begin()) {
        --pre;
        int s = *pre + 1;
        int t = dfn[x];

        node u = rmq(s, t);
        if (u.val > maxn) {
            maxn = u.val;
            p = u.x;
        }
    }

    if (suf != f.end()) {
        int t = *suf;
        int s = dfn[x] + 1;

        node u = rmq(s, t);
        if (u.val > maxn) {
            maxn = u.val;
            p = u.x;
        }
    }
    ans -= val[fa[p]];
}

void del (int x) {
    int maxn = -1;
    int p;

    auto cur = f.find(dfn[x]);
    auto suf = cur;
    ++suf;
    f.erase(cur);
    auto pre = suf;
    if (pre != f.begin()) {
        --pre;
        int s = *pre + 1;
        int t = dfn[x];

        node u = rmq(s, t);
        if (u.val > maxn) {
            maxn = u.val;
            p = u.x;
        }
    }
    if (suf != f.end()) {
        int t = *suf;
        int s = dfn[x] + 1;

        node u = rmq(s, t);
        if (u.val > maxn) {
            maxn = u.val;
            p = u.x;
        }
    }
    ans += val[fa[p]];
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    lg[0] = -1;
    for (int i = 1; i <= 2e5; ++i) {
        lg[i] = lg[i / 2] + 1;
    }

    std::cin >> n >> m >> q;
    B = sqrt(n / 2);
    for (int i = 1; i <= m; ++i) {
        std::cin >> e[i].u >> e[i].v >> e[i].w;
        ++e[i].u, ++e[i].v;
    }
    std::sort(e + 1, e + m + 1);

    DSU dsu(n * 2 - 1);
    dsu.init(); 
    tot = n;
    for (int i = 1; i <= m; ++i) {
        int fu = dsu.find(e[i].u);
        int fv = dsu.find(e[i].v);
        if (fu != fv) {
            s += e[i].w;
            dsu.fa[fu] = dsu.fa[fv] = ++tot;

            val[tot] = e[i].w;
            mst[tot].push_back(fu);
            mst[tot].push_back(fv);
        }
    }

    dfs(n * 2 - 1, 0);
    for (int j = 1; j <= 19; ++j) {
        for (int i = 1; i <= n * 2 - 1 - (1 << j) + 1; ++i) {
            st[i][j] = std::min(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
            if (st[i][j] == st[i][j - 1]) {
                stid[i][j] = stid[i][j - 1];
            } else {
                stid[i][j] = stid[i + (1 << j - 1)][j - 1];
            }
        }
    }

    for (int i = 1; i <= q; ++i) {
        std::cin >> ask[i].l >> ask[i].r;
        ++ask[i].l, ++ask[i].r;
        ask[i].id = i;
    }
    std::sort(ask + 1, ask + q + 1);

    ans = s;
    int nl = 1, nr = 0;
    for (int i = 1; i <= q; ++i) {
        while (nl > ask[i].l) {
            add(--nl);
        }
        while (nr < ask[i].r) {
            add(++nr);
        }
        while (nl < ask[i].l) {
            del(nl++);
        }
        while (nr > ask[i].r) {
            del(nr--);
        }
        ask[i].ans = ans;
    }

    std::sort(ask + 1, ask + q + 1, cmp);
    for (int i = 1; i <= q; ++i) {
        std::cout << ask[i].ans << std::endl;
    }

    return 0;
}

::::

提交记录

Part 5

我们发现添加和删除复杂度还是太劣了。

发现，我们可以记录前驱和后继。每次删除的时候直接把前驱和后继处理一下就能够 O(1) 实现。但是这个时候添加操作的复杂度仍然是 O(\log n)。但是！看到只允许删除，不允许添加，你想到了什么？回滚莫队！

没学过回滚莫队的建议先去看板子，里面题解应该是讲得比较详细的。这里简单提一下。

考虑把询问的 l 逐块处理，到新的块的时候全部推翻重来，将前驱后继全部重新处理。这里可以先记录另一个前驱后继，右端点为 n，左端点不断增加。显然只有删除操作。

对于同一个块中的，我们考虑先记录这个块的左端点，然后右端点原来先从大到小排好序，一开始从 n 开始，不断删除。对于左边的，从这个块的左端点往右删除，用一个栈记录变化。当这一次询问处理结束之后，根据栈内记录的信息，往回推。

最后时间复杂度是 O(n \sqrt n)，稍微卡一卡常就过了。

::::info[100 分代码]

#include <bits/stdc++.h>

using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;

const int MAXN = 2e5 + 10;
const int INF  = 1e9;

struct node {
    int x;
    i64 val;

    bool operator < (const node &tmp) const {
        return x < tmp.x;
    }
};

struct DSU {
    int n;
    std::vector <int> fa;
    DSU (int n_) : n(n_), fa(n + 10) {};

    void init() {
        for (int i = 1; i <= n; ++i) {
            fa[i] = i;
        }
    }

    int find (int x) {
        return fa[x] == x ? x : fa[x] = find(fa[x]);
    }
};

struct OPERATE {
    int pre, x, suf;
};

struct EDGE {
    int u, v;
    i64 w;

    bool operator < (const EDGE &tmp) const {
        return w < tmp.w;
    }
};

struct EDGE2 {
    int to, w;
};

int B;
int block[MAXN];

struct QUESTION {
    int l, r, id;
    i64 ans;

    bool operator < (const QUESTION &tmp) const {
        int nl = block[l];
        int pl = block[tmp.l];
        if (nl == pl) {
            return tmp.r < r;
        }
        return nl < pl;
    }
};

bool cmp (QUESTION x, QUESTION y) {
    return x.id < y.id;
}

int n, m, q;
int dep[MAXN];
int dfn[MAXN];
int st[MAXN][20];
int stid[MAXN][20];

int tot;
int tot1;

int fa[MAXN];

i64 val[MAXN];
i64 tag[MAXN];

i64 s, ans;

EDGE e[MAXN];
QUESTION ask[MAXN];

std::vector <int> edge;
std::vector <int> mst[MAXN];
std::vector <node> pos[MAXN];

void dfs (int x, int lst) {
    dfn[x] = ++tot1;
    fa[dfn[x]] = lst;
    dep[x] = dep[lst] + 1;
    st[dfn[x]][0] = st[dfn[lst]][0] + 1;
    stid[dfn[x]][0] = dfn[x];

    for (auto to : mst[x]) {
        if (to == lst) {
            continue;
        }

        dfs(to, x);
    }
}

int lg[MAXN];
int o[MAXN];

int now_block;
int gpre[MAXN];
int gsuf[MAXN];
int tpre[MAXN];
int tsuf[MAXN];

i64 tval, res;

std::set <int> f;

inline node rmq (int l, int r) {
    if (l > r) std::swap(l, r);
    int k = lg[r - l + 1];
    int k1 = st[l][k], k2 = st[r - (1 << k) + 1][k];
    if (k1 < k2) {
        return (node){stid[l][k], k1};
    } else {
        return (node){stid[r - (1 << k) + 1][k], k2};
    }
}

int tp;
OPERATE stk[MAXN];

inline void add (int pre, int x, int suf, i64 &tval) {
    int maxn = -1;
    int p;

    if (!pre && !suf) {
        return;
    }
    if (pre) {
        int s = pre + 1;
        int t = x;

        node u = rmq(s, t);
        if (u.val > maxn) {
            maxn = u.val;
            p = u.x;
        }
    }
    if (suf) {
        int t = suf;
        int s = x + 1;

        node u = rmq(s, t);
        if (u.val > maxn) {
            maxn = u.val;
            p = u.x;
        }
    }
    tval -= val[fa[p]];
}

inline void del (int x, bool opt, i64 &tval) {
    int maxn = -1;
    int p;

    int pre = tpre[x];
    int suf = tsuf[x];

    if (!pre && !suf) {
        return;
    }
    if (pre) {
        int s = pre + 1;
        int t = x;

        node u = rmq(s, t);
        if (u.val > maxn) {
            maxn = u.val;
            p = u.x;
        }
    }
    if (suf) {
        int t = suf;
        int s = x + 1;

        node u = rmq(s, t);
        if (u.val > maxn) {
            maxn = u.val;
            p = u.x;
        }
    }
    tval += val[fa[p]];

    if (opt) {
        stk[++tp]=(OPERATE){pre, x, suf};
    }
    tsuf[pre] = suf;
    tpre[suf] = pre;
}
inline void del2 (int x, bool opt, i64 &tval) {
    int maxn = -1;
    int p;

    int pre = gpre[x];
    int suf = gsuf[x];

    if (!pre && !suf) {
        return;
    }
    if (pre) {
        int s = pre + 1;
        int t = x;

        node u = rmq(s, t);
        if (u.val > maxn) {
            maxn = u.val;
            p = u.x;
        }
    }
    if (suf) {
        int t = suf;
        int s = x + 1;

        node u = rmq(s, t);
        if (u.val > maxn) {
            maxn = u.val;
            p = u.x;
        }
    }
    tval += val[fa[p]];

    if (opt) {
        stk[++tp]=(OPERATE){pre, x, suf};
    }
    gsuf[pre] = suf;
    gpre[suf] = pre;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::cin >> n >> m >> q;
    B = 380;
    lg[0] = -1;
    for (int i = 1; i <= 2e5; ++i) {
        lg[i] = lg[i / 2] + 1;
        block[i] = (i + B - 1) / B;
    }
    for (int i = 1; i <= m; ++i) {
        std::cin >> e[i].u >> e[i].v >> e[i].w;
        ++e[i].u, ++e[i].v;
    }
    std::sort(e + 1, e + m + 1);

    DSU dsu(n * 2 - 1);
    dsu.init(); 
    tot = n;
    for (int i = 1; i <= m; ++i) {
        int fu = dsu.find(e[i].u);
        int fv = dsu.find(e[i].v);
        if (fu != fv) {
            s += e[i].w;
            dsu.fa[fu] = dsu.fa[fv] = ++tot;

            val[tot] = e[i].w;
            mst[tot].push_back(fu);
            mst[tot].push_back(fv);
        }
    }

    dfs(n * 2 - 1, 0);
    for (int j = 1; j <= 17; ++j) {
        for (int i = 1; i <= n * 2 - 1 - (1 << j) + 1; ++i) {
            st[i][j] = std::min(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
            if (st[i][j] == st[i][j - 1]) {
                stid[i][j] = stid[i][j - 1];
            } else {
                stid[i][j] = stid[i + (1 << j - 1)][j - 1];
            }
        }
    }

    for (int i = 1; i <= q; ++i) {
        std::cin >> ask[i].l >> ask[i].r;
        ++ask[i].l, ++ask[i].r;
        ask[i].id = i;
    }
    std::sort(ask + 1, ask + q + 1);

    std::vector <int> e;
    for (int i = 1; i <= n; ++i) {
        e.push_back(dfn[i]);
    }
    std::sort(e.begin(), e.end());
    for (int i = 0; i < e.size(); ++i) {
        if (i) {
            gpre[e[i]] = e[i - 1];
        }
        if (i < e.size() - 1) {
            gsuf[e[i]] = e[i + 1];
        }
    }

    ans = s;
    int nl = 1, nr = 0;

    now_block = 0;
    for (int i = 1; i <= q; ++i) {
        if (block[ask[i].l] != now_block) {
            while (now_block != block[ask[i].l]) {
                if (now_block >= 1) {
                    int tl = (now_block - 1) * B + 1;
                    int tr = now_block * B;
                    for (int j = tl; j <= tr; ++j) {
                        del2(dfn[j], 0, tval);
                    }
                }

                ++now_block;
            }
            for (int j = std::max(1, (now_block - 1) * B + 1); j <= n; ++j) {
                tpre[dfn[j]] = gpre[dfn[j]], tsuf[dfn[j]] = gsuf[dfn[j]];
            }
            res = tval;

            nl = (now_block - 1) * B + 1;
            nr = n;
        }

        while (nr > ask[i].r) {
            del(dfn[nr], 0, res);
            --nr;
        }

        int el = nl;
        while (el < ask[i].l) {
            del(dfn[el], 1, res);
            ++el;
        }

        //std::cout << "O:" << ask[i].l << ' ' << ask[i].r << ' ' << res << std::endl;
        ask[i].ans = res;
        while (tp) {
            OPERATE tmp = stk[tp--];

            tsuf[tmp.pre] = tmp.x;
            tpre[tmp.suf] = tmp.x;

            tpre[tmp.x] = tmp.pre;
            tsuf[tmp.x] = tmp.suf;
            add(tmp.pre, tmp.x, tmp.suf, res);
        }
    }

    std::sort(ask + 1, ask + q + 1, cmp);
    for (int i = 1; i <= q; ++i) {
        std::cout << ask[i].ans << "\n";
    }

    return 0;
}

::::

提交记录

后记

本人的实现方式真的是太离谱了（（（

如果有错误请指出。