算法竞赛比赛记录: 北京大学 2024 年《数据结构与算法A（实验班）》期末考试

D. MST

算法流程

先对 “(边权, ID)” 进行排序（从小到大）
初始化……
1. 并查集，两颗线段树（一棵维护从左向右的字符串哈希值，另一棵维护从右向左的字符串哈希值）
2. 给并查集上的每一个连通块分配一个随机数（ $n$ 个，初始时并查集都不连通）
3. 初始化 vector，记录一下每一个连通块内的所有点
遍历排序过的边…… $(w,id)$
1. 首先，计算一下 $id$ 对应的边集， $(1,id-1), (2,id-2), \dots, (\frac{id-1}{2}, id-\frac{id-1}{2})$
2. 从 $l=\frac{id-1}{2},r=id-\frac{id-1}{2}$ 开始向外二分查找下一条要连接的边 $(l-M, r+M)$
  1. 在并查集上连接这一条边对应的两个点 $l-M,r+M$ ，
  2. 同时维护 vector（更新同一个连通块内的点，这里需要用启发式合并）。
  3. 维护 vector 的同时，在线段树上同步修改对应点的值（修改成新连通块的值），即同步维护字符串的哈希值。
3. 每合并两个点，就把边权加入答案
最后输出答案

正确性证明

考虑根据 Kruskal 算法的思路，我们总是尝试从边权最小的边 $e=(u,v)$ 开始尝试加入 MST，如果 $(u,v)$ 在并查集里不连通，那么就说明这条边可以加入 MST.

现在的话，边都是以 $a_{i+j}$ 的形式给出，例如对于 $a_k$ ，它所代表的边为 $(1,k-1),(2,k-2),\dots$ 。

如果我们给并查集里的每一个连通块分配一个字母，那么考虑并查集里的两个点 $i,j$ 且我们正在考虑 $a_k$ 满足 $k=i+j$ ：那么我们可以发现的一点是，如果 $i,j$ 已经连通，那么他们的字母应该是相同的，否则就不相同。如果字母相同，我们就不需要在 $(i,j)$ 之间连边，因为他们已经在同一个连通块里（根据 Kruskal 算法，加入 $(i,j)$ 这条边会产生一个环）；否则我们就可以加入这条边，在并查集里把他们连起来。

然后我们就可以发现一件事：如果对每一条 $a_k$ 对应的边 $(i,j)$ 来说，都不需要向 MST 里添加这条边，这意味着 $i,j$ 对应的值相等；而 $i+j=k$ ，因此总是有 $val[i]=val[k-i]$ ，也就是说 $a_k$ 所对应的点 $1\dots k-1$ 是回文串！

这意味着我们可以通过不断判断某一段前后缀是否回文，来看这一段前后缀是不是已经在并查集（也即 MST）上连接完毕。我们可以用二分快速进行查找和判断。

时间复杂度分析

根据 MST 的性质，MST 是一棵树，最多 $n-1$ 条边，而因为每一次二分必将连接一条边，因此“二分枚举待连接的边”这个操作最多进行 $n-1$ 次，即 $O(n)$ 次。每一次二分最多在包含 $n$ 条边的集合内搜索，因此二分次数是 $O(n\log n)$ 的。每一次二分都需要在线段树上进行区间查询，而单次区间查询是 $O(\log n)$ 的，所有二分部分的时间复杂度是 $O(n\log^2 n)$

接着考虑启发式合并部分的复杂度。由于每一次都将小的集合添加到大的集合里，因此每一次合并，被添加的元素所在的集合大小都会翻倍，由于最多有 $n$ 个点，因此最坏情况下一个元素会被添加 $\log n$ 次，因此启发式合并一共会产生 $O(n\log n)$ 次添加元素操作。

但是在每次添加元素的时候，我们还要维护线段树，对单点修改、区间查询线段树而言，修改一次的复杂度是 $O(\log n)$ ，因此启发式合并以及维护线段树的总体复杂度就是 $O(n\log^2 n)$

因此总体时间复杂度为 $O(n\log^2n)$

Code

#include <algorithm>
#include <cassert>
#include <functional>
#include <iostream>
#include <numeric>
#include <random>
#include <utility>
#include <vector>

using u64       = unsigned long long;
constexpr u64 P = 4816069;
std::mt19937_64 rng(std::random_device{}());
std::vector<u64> base, rd;

struct ModTree {
    struct Node {
        int l, r;
        u64 fhash, bhash;
    };
    std::vector<Node> tree;
    int n;

    Node update(Node l, Node r) {
        Node res;
        res.l = l.l, res.r = r.r;
        res.fhash = l.fhash * base[r.r - r.l + 1] + r.fhash;
        res.bhash = r.bhash * base[l.r - l.l + 1] + l.bhash;
        return res;
    }
    void init(int n) {
        tree.assign(n * 4, Node());
        this->n = n;
    }
    void build(std::vector<u64> &vec, int p, int l, int r) {
        tree[p].l = l, tree[p].r = r;
        if (l == r) {
            tree[p].fhash = tree[p].bhash = vec[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(vec, p << 1, l, mid);
        build(vec, p << 1 | 1, mid + 1, r);
        tree[p] = update(tree[p << 1], tree[p << 1 | 1]);
    }
    void modify(int p, int pos, u64 val) {
        if (tree[p].l == tree[p].r) {
            tree[p].fhash = tree[p].bhash = val;
            return;
        }
        int mid = (tree[p].l + tree[p].r) >> 1;
        if (pos <= mid) modify(p << 1, pos, val);
        else modify(p << 1 | 1, pos, val);
        tree[p] = update(tree[p << 1], tree[p << 1 | 1]);
    }
    Node query(int p, int l, int r) {
        if (l <= tree[p].l && tree[p].r <= r) return tree[p];
        int mid = (tree[p].l + tree[p].r) >> 1;
        if (r <= mid) return query(p << 1, l, r);
        else if (l > mid) return query(p << 1 | 1, l, r);
        Node res = update(query(p << 1, l, mid), query(p << 1 | 1, mid + 1, r));
        return res;
    }
};

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

    int n;
    std::cin >> n;
    [&] {
        base.resize(n + 1), rd.resize(n + 1);
        base[0] = 1;
        for (int i = 1; i <= n; i++) base[i] = base[i - 1] * P, rd[i] = rng();
    }();
    std::vector<std::pair<u64, int>> vec;
    std::vector<std::vector<int>> nodes(n + 1);
    for (int i = 3; i < n * 2; i++) {
        u64 x;
        std::cin >> x;
        vec.emplace_back(x, i);
    }

    std::vector<int> fa(n + 1, 0);
    std::iota(fa.begin(), fa.end(), 0);
    std::function<int(int)> find = [&](int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); };

    ModTree tree;
    tree.init(n);
    tree.build(rd, 1, 1, n);
    for (int i = 1; i <= n; i++) nodes[i].push_back(i);

    auto unite = [&](int u, int v) {
        u = find(u), v = find(v);
        if (u == v) return;
        if (nodes[u].size() > nodes[v].size()) std::swap(u, v);
        fa[u] = v;
        for (int i : nodes[u]) {
            nodes[v].emplace_back(i);
            rd[i] = rd[v];
            tree.modify(1, i, rd[i]);
        }
        nodes[u].clear();
    };

    std::sort(vec.begin(), vec.end());

    long long ans = 0;
    for (auto &[E, id] : vec) {
        int l = (id - 1) / 2, r = id - l;
        int size = std::min(l, n - r + 1);
        int L = l - size + 1, R = r + size - 1;

        while (r <= R) {
            // std::cerr << l << ' ' << r << ' ' << L << ' ' << R << '\n';
            // std::cerr << tree.query(1, L, l).fhash << ' ' << tree.query(1, r, R).bhash << '\n';
            // for (int i = 1; i <= n; i++) std::cerr << i << ": " << rd[i] << '\n';
            if (tree.query(1, L, l).fhash == tree.query(1, r, R).bhash) break;

            int lb = 0, ub = R - r;
            while (lb <= ub) {
                int mid = (lb + ub) >> 1;
                if (tree.query(1, l - mid, l).fhash != tree.query(1, r, r + mid).bhash) ub = mid - 1;
                else lb = mid + 1;
            }

            l -= lb, r += lb;
            unite(l, r);
            ans += E;
        }
    }
    std::cout << ans << '\n';

    return 0;
}