【P9216】写大作业

· · 题解

【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';
}