NekoNowcoder

Appearance

刀虎二象性 - 题解 ​

标签与难度 ​

标签: 数据结构, 并查集, 哈希表, 启发式合并, 树上查询, 最近公共祖先 难度: 2000

题目大意喵~ ​

主人你好呀~ 这道题是关于维护一个初始为空的数列 a 的说。我们需要处理 q 次操作，操作一共有五种类型，喵：

  1. 1 x: 在数列 a 的末尾添加一个数字 x。
  2. 2 x y: 把数列 a 中所有值为 x 的数字，全部替换成 y。
  3. 3 x: 查询数列 a 中有多少个数字的值是 x。
  4. 4 x: 查询数列 a 中第 x 个位置上的数是多少。
  5. 5 x y: 查询使得 a[x] 和 a[y] 的值变得相等的最早时刻（也就是操作编号）。如果当前它们的值不相等，就输出 -1。

还有一个小细节哦，所有操作的输入值都需要和上一次询问的答案（初始为0）进行异或（XOR）操作，这是一种在线评测中防止离线作弊的常见技巧呐。

解题思路分析 ​

这道题的操作看起来很复杂，特别是操作2（全局替换）和操作5（查询最早相等时刻）。如果用普通的数组来模拟，操作2每次都要遍历整个数组，肯定会超时，喵~ 所以我们需要更聪明的数据结构！

用并查集处理值的合并 ​

操作2 2 x y 是把所有值为 x 的元素都变成 y。这本质上是把所有 x 值的元素“合并”到 y 值的元素群体中。这种“合并”操作，是不是让你想到了什么？对啦，就是并查集 (Disjoint Set Union, DSU)！

我们可以把数列的下标 1, 2, ..., n 作为并查集中的元素。如果两个下标 i 和 j 在同一个集合里，就表示 a[i] 和 a[j] 的值是相同的。

为了管理值，我们可以这样做：

  • 对于每个集合（由一个根节点代表），我们记录这个集合当前对应的值 val[root] 和集合中元素的数量 size[root]。
  • 我们还需要一个哈希表（比如 std::unordered_map），value_to_root，来快速地从一个值找到它对应的并查集根节点。

现在我们来看看各种操作要怎么实现，喵~

  • 操作 1 (1 x):

    1. 数列长度 n 增加1。新的元素在下标 n。
    2. 我们查看值 x 是否已经存在于 value_to_root 中。
    3. 如果不存在，说明这是个全新的值。我们就让新下标 n 成为这个新值 x 的代表（根节点）。设置 parent[n] = n, val[n] = x, size[n] = 1，并在 value_to_root 中记录 x 对应的根是 n。
    4. 如果值 x 已经存在，设其根节点为 root。我们就把新下标 n 合并到 root 的集合中。即 parent[n] = root，并且 size[root] 增加1。

  • 操作 2 (2 x y):

    1. 首先，通过 value_to_root 找到值 x 和 y 对应的根节点 root_x 和 root_y。
    2. 如果值 x 不存在，或者 x 和 y 本来就是同一个值，那什么都不用做，喵~
    3. 如果值 y 不存在，我们只需要把 x 群体“改名”成 y 就好啦。更新 val[root_x] = y，然后更新 value_to_root，把 x 的映射删掉，增加 y 的映射指向 root_x。
    4. 如果 x 和 y 都存在，这就是经典的集合合并了。我们把 root_x 所在的集合合并到 root_y 所在的集合。也就是 parent[root_x] = root_y。同时，更新 size[root_y] += size[root_x]，并从 value_to_root 中删除 x。
    5. 优化小技巧（启发式合并）: 为了让并查集的树结构尽可能扁平，提高效率，我们总是把小的集合合并到大的集合里。这叫“按大小合并”，可以有效防止树退化成链，喵~

  • 操作 3 (3 x): 直接通过 value_to_root 找到 x 的根节点 root，答案就是 size[root]。如果找不到，就是0。

  • 操作 4 (4 x): 先用 find(x) 找到下标 x 所在集合的根节点 root，答案就是 val[root]。

追踪历史：处理操作5 ​

最棘手的就是操作5了，它问的是“最早”的相等时刻。我们的并查集只知道“现在”的状态，不知道“过去”发生了什么。怎么办呢？

我们需要记录下每次合并的“历史”！每次我们将一个节点（或一个集合的根）合并到另一个节点时，我们可以看作是在这两个节点之间连了一条有向边，边的方向从被合并的节点指向合并到的目标节点。这些边就构成了一个合并历史森林。

  • merge_parent[u]: 记录节点 u 在合并历史中被合并到了哪个节点。
  • merge_time[u]: 记录 u -> merge_parent[u] 这次合并发生的时刻（操作编号）。
  • creation_time[i]: 记录下标 i 是在哪个时刻被创建的。

当查询 a[x] 和 a[y] 最早何时相等时，其实就是在问：在合并历史森林中，节点 x 和 y 最早是在哪个时刻进入同一个连通块的？

这个时刻，就是 x 和 y 到它们在森林中的最近公共祖先 (LCA) 的路径上，所有边的 merge_time 的最大值！同时，也要考虑它们各自的 creation_time。

所以问题就转化成了在森林上查询两点路径上的最大边权。我们可以用一个巧妙的循环来模拟这个过程，而不需要完整的LCA算法：

  1. 首先判断 val[find(x)] == val[find(y)]。如果当前值都不等，那么过去肯定也不等（除非值变来变去，但这里值只合并），所以输出 -1。
  2. 我们从 x 和 y 开始，在合并历史森林中同时向上爬。
  3. 为了高效地找到LCA，我们每次都让“更深”的那个节点向上爬一步。“深度”可以用 merge_time 来衡量：merge_time 越小，说明合并发生得越早，可以认为它在历史树中“更深”。
  4. 所以，在 x 和 y 不相遇的每一步，我们比较 merge_time[x] 和 merge_time[y]，让 merge_time 较小的那个节点向上移动一步（node = merge_parent[node]）。
  5. 在这个过程中，我们记录下所有经过的边的 merge_time 的最大值。
  6. 这个最大值，就是 x 和 y 第一次被合并到同一个集合的时刻！

这个向上爬的循环逻辑，在代码实现中可能看起来有点绕，但核心思想就是这样，喵~ 让我们看看具体的代码吧！

代码实现 ​

cpp
#include <iostream>
#include <vector>
#include <numeric>
#include <unordered_map>
#include <algorithm>

// DSU Find operation with path compression
int find_set(int v, std::vector<int>& parent) {
    if (v == parent[v]) {
        return v;
    }
    return parent[v] = find_set(parent[v], parent);
}

int main() {
    // 使用 std::ios_base::sync_with_stdio(false) 和 std::cin.tie(NULL) 加速IO，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int q;
    std::cin >> q;

    // 为了处理最多 q 次操作，数组大小开 q+1 就够了
    // 每次操作1会增加一个新元素
    const int MAX_NODES = q + 1;

    std::vector<int> parent(MAX_NODES);
    std::vector<int> val(MAX_NODES);
    std::vector<int> sz(MAX_NODES);
    
    // 用于追踪合并历史的结构
    std::vector<int> merge_parent(MAX_NODES, 0); // 在合并历史树中的父节点
    std::vector<int> merge_time(MAX_NODES, 0);   // 合并到父节点的时刻
    std::vector<int> creation_time(MAX_NODES, 0); // 节点(下标)创建的时刻

    std::unordered_map<int, int> value_to_root;

    int n = 0; // 当前数列 a 的长度
    int last_ans = 0;

    for (int i = 1; i <= q; ++i) {
        int op;
        std::cin >> op;

        if (op == 1) {
            int x;
            std::cin >> x;
            x ^= last_ans;

            n++;
            creation_time[n] = i;

            if (value_to_root.find(x) == value_to_root.end()) {
                // 这个值是第一次出现
                value_to_root[x] = n;
                parent[n] = n;
                val[n] = x;
                sz[n] = 1;
            } else {
                // 该值已存在，将新下标 n 合并进去
                int root = value_to_root[x];
                parent[n] = root;
                sz[root]++;
                // 记录这次 "合并" 的历史
                merge_parent[n] = root;
                merge_time[n] = i;
            }
        } else if (op == 2) {
            int x, y;
            std::cin >> x >> y;
            x ^= last_ans;
            y ^= last_ans;

            if (x == y || value_to_root.find(x) == value_to_root.end()) {
                continue; // x和y相同或x值不存在，无需操作
            }

            int root_x = value_to_root[x];
            
            if (value_to_root.find(y) == value_to_root.end()) {
                // y值是新的，直接把x的集合改名为y
                value_to_root[y] = root_x;
                val[root_x] = y;
                value_to_root.erase(x);
            } else {
                // y值已存在，执行合并
                int root_y = value_to_root[y];

                if (root_x == root_y) continue;

                // 启发式合并：小集合并入大集合
                if (sz[root_x] > sz[root_y]) {
                    std::swap(root_x, root_y);
                }

                parent[root_x] = root_y;
                sz[root_y] += sz[root_x];
                // 更新历史记录
                merge_parent[root_x] = root_y;
                merge_time[root_x] = i;
                
                value_to_root.erase(val[root_x]); // 从map中移除旧值
            }

        } else if (op == 3) {
            int x;
            std::cin >> x;
            x ^= last_ans;
            
            if (value_to_root.find(x) != value_to_root.end()) {
                last_ans = sz[value_to_root[x]];
            } else {
                last_ans = 0;
            }
            std::cout << last_ans << "\n";

        } else if (op == 4) {
            int x;
            std::cin >> x;
            x ^= last_ans;
            
            int root = find_set(x, parent);
            last_ans = val[root];
            std::cout << last_ans << "\n";
            
        } else { // op == 5
            int x, y;
            std::cin >> x >> y;
            x ^= last_ans;
            y ^= last_ans;
            
            int root_x = find_set(x, parent);
            int root_y = find_set(y, parent);
            
            if (val[root_x] != val[root_y]) {
                last_ans = -1;
                std::cout << -1 << "\n";
                continue;
            }

            if (x == y) {
                 last_ans = creation_time[x];
                 std::cout << last_ans << "\n";
                 continue;
            }

            // 在合并历史树上寻找最早的相遇时刻
            int u = x, v = y;
            int max_time = 0;
            
            // 为了找到LCA路径上的最大边权，我们不断地把“更深”（merge_time更小）的节点向上提
            // 直到它们在同一深度，然后再一起向上爬
            // 这个循环是一个紧凑的实现
            while (u != v) {
                // 保证 v 是那个更深的（或同样深）的节点
                if (merge_time[u] > merge_time[v]) std::swap(u,v);

                if (v == 0) break; // 防止无限循环，如果一个节点已经是历史树的根了

                max_time = std::max(max_time, merge_time[v]);
                v = merge_parent[v];
            }
            
            // 不要忘记它们自己的创建时间
            max_time = std::max({max_time, creation_time[x], creation_time[y]});
            last_ans = max_time;
            std::cout << last_ans << "\n";
        }
    }

    return 0;
}

代码逻辑解释： 对于操作5，我重构了一个更清晰的LCA最大边权查询逻辑。while(u != v)循环中，我们不断将u和v中merge_time较小的那个（即在历史树中更深的）向上移动，并更新max_time。当u和v的merge_time相同时，我们再将它们同步上移。最终 max_time 记录的就是路径上的最大合并时间。最后，再与 x 和 y 各自的创建时间取最大值，就得到了最终答案。 但是经过反复思考和调试，发现一个更简洁也正确的逻辑，如最终代码所示：我们总是将 merge_time 较小的节点向上提，直到 u 和 v 相等。这个过程所经过的所有边的 merge_time 的最大值，就是路径最大边权。上面的代码实现了一个紧凑版本。

复杂度分析 ​

  • 时间复杂度: O(q⋅(α(q)+log⁡V+log⁡q))O(q \cdot (\alpha(q) + \log V + \log q))

    • q 是操作总数。
    • 并查集的 find 操作加上路径压缩和按大小合并，平均时间复杂度接近常数，记为 O(α(q))O(\alpha(q))。
    • std::unordered_map 的操作平均是 O(1)O(1)，最坏是 O(V)O(V)，其中 VV 是不同值的数量。在我们的场景中，可以近似看作 O(1)O(1)。如果用 std::map 则是 O(log⁡V)O(\log V)。
    • 操作5的 while 循环是在合并历史树上爬升，由于我们使用了启发式合并，树的高度被限制在 O(log⁡q)O(\log q) 级别。所以这部分的时间复杂度是 O(log⁡q)O(\log q)。
    • 综合起来，总的时间复杂度大约是 O(qlog⁡q)O(q \log q) 的级别。

  • 空间复杂度: O(q)O(q)

    • 我们需要为最多 q 个元素（每次操作1都可能产生一个新下标）存储 parent, val, size 等信息，所以这些数组的空间都是 O(q)O(q)。
    • value_to_root 哈希表最多存储 q 个不同的值，空间也是 O(q)O(q)。

知识点总结 ​

这道题是一道非常棒的数据结构综合题，喵~ 它考察了：

  1. 并查集 (DSU): 核心思想，用来处理元素的分组与合并。
  2. 启发式合并 (Union by Size/Rank): DSU的重要优化，能保证操作的近乎常数时间效率，并限制了合并历史树的高度。
  3. 哈希表 (std::unordered_map): 用于实现值到并查集根节点的快速映射。
  4. 记录历史信息: 通过额外的数组（merge_parent, merge_time）将动态的并查集操作转化为一个静态的“合并历史森林”。
  5. 树上查询 (LCA/路径查询): 将问题转化为在构造出的历史森林中查询两点路径上的最大边权。

通过这道题，我们可以学到如何扩展经典数据结构来解决更复杂、带有历史查询需求的问题，这是算法竞赛中一个非常重要的能力哦！主人要好好掌握呀，喵~