自动搬运

查看原文

来自洛谷，原作者为

	一扶苏一 休息结束。邮箱 yifusuyi@qq.com

搬运于2025-08-24 22:46:27，当前版本为作者最后更新于2023-04-24 11:00:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

【HASH】【P9216】写大作业

磕头：
出题时不知道新科技，被随机 hash 老哥直接 $O(q)$ 爆标了，成了典题。这篇题解是 std 的启发式合并做法。

Analysis

以下设 $m = \sum_{i = 1}^n m_i$。

首先思考『相似』的定义，容易发现数列 $a$ 和 $b$ 相似等价于任意整数在 $a$ 和 $b$ 中的出现次数相同。

于是考虑维护每个数字在每个数列里的出现次数，对每个数列开一个 map 存一下即可。如果两个数列对应的 map 相同，那么它们相似。

考虑合并两个数列，就是合并两个 map。注意到题意是合并完一个数列以后被合并的数列就被扔掉了，自然考虑启发式合并。合并两个 map 时，枚举较小的 map 里的元素，然后暴力做单点插入到另一个 map 中。注意到一个数字每被枚举到一次，它所属的集合大小至少翻倍，所以至多被枚举 $\log m$ 次。把所有数列都合并起来的复杂度就是 $O(m \log m)$。

接下来处理判定两个 map 相同，考虑 hash。为了迎合启发式合并的单点插入，我们的 hash 函数必须能直接计算单个数字的贡献。std 的做法是：对一个 map 定义 hash 函数 $f$，如果数字 $x$ 在数列里出现了 $y$ 次（即 map 里键值 $x$ 对应的权值是 $y$），那么对 $f$ 产生 $x^{ky}$ 的贡献。其中 $k$ 是规定的常量。std 里取了 $k = 1,2,3,4,5$。

在合并两个集合时，假设把 map $a$ 里的元素插入到 $b$ 中，$x$ 在 $a$ 里的权值是 $y_1$，在 $b$ 的权值是 $y_2$，那么对 $b$ 的 hash 函数的影响是：$- 2^{y_1} + 2^{y_1 + y_2}$。

数据保证了随机，没有卡自然溢出，直接用 unsigned long long 自然溢出 hash 值即可。

这样，我们可以在做启发式合并的同时 $O(\log m)$ 地维护 hash 值的变化，所以启发式合并的总时间复杂度就是 $O(m \log^2 m)$。同时可以 $O(1)$ 回答每次询问。所以算法的总时间复杂度为 $O(m \log ^2 m + q)$。

Code

#include "assert.h"
#include <map>
#include <iostream>

const int maxn = 100005;
const int maxJ = 5;

typedef unsigned long long int ull;

ull mpow(ull x, int y) {
  ull ret = 1;
  while (y) {
    if (y & 1) ret *= x;
    x *= x;
    y >>= 1;
  }
  return ret;
}

ull hash[maxJ][maxn];
std::map<int, int> rec[maxn];
bool oc[maxn];

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int n, q;
  std::cin >> n >> q;
  for (int i = 1, m, x; i <= n; ++i) {
    for (std::cin >> m; m; --m) {
      std::cin >> x;
      ++rec[i][x];
    }
    for (int j = 0; j < maxJ; ++j) {
      for (auto &[x, y] : rec[i]) {
        hash[j][i] += mpow(x, j * y);
      }
    }
  }
  int ans = 0;
  for (int i = 1, o, x, y; i <= q; ++i) {
    std::cin >> o >> x >> y;
    if (o == 2) {
      bool ret = true;
      for (int j = 0; j < maxJ; ++j) if (hash[j][x] != hash[j][y]) {
        ret = false; break;
      }
      if (ret) ans ^= i;
    } else {
      assert(oc[x] == false);
      oc[x] = true;
      if (rec[x].size() > rec[y].size()) {
        rec[x].swap(rec[y]);
        for (int j = 0; j < maxJ; ++j) std::swap(hash[j][x], hash[j][y]);
      }
      for (auto &[u, v] : rec[x]) {
        if (rec[y][u]) for (int j = 0; j < maxJ; ++j) hash[j][y] -= mpow(u, j * rec[y][u]);
        for (int j = 0; j < maxJ; ++j) hash[j][y] += mpow(u, v * j);
      }
    }
  }
  std::cout << ans << '\n';
}