AT_abc329_f

· · 题解

闲话

来点不同的大炮打蚊子的非 STL 的做法。

题目翻译

你有 n 个盒子，每个盒子一开始装了一个颜色为 c_i 的球。

有 q 次询问（操作），每次询问给出一对 (a,b)，要把盒子 a 的所有球转到盒子 b 里，问此时 b 里有多少颜色不同的球。

# 题目思路 考虑使用根号分治。 显然的阈值为 $B=\sqrt n\approx 450$。 对于目前球个数 $\geq B$ 的盒子，我们记录一个桶 $bkt_{i,j}$ 表示**序号（不是编号）为 $i$** 的盒子是否装了 $j$。 因为这样的盒子数只有 $\leq B$ 个，所以我们需要记录一个序号，设编号为 $i$ 的盒子的序号为 $id_i$。 然后对于装球个数 $\lt B$ 的盒子，我们记录 $arr_{i,j}$ 表示**编号为 $i$** 的盒子的第 $j$ 个装的是什么。 大和大在一起，我们可以直接 $O(n)$ 转移。可以证明这样子转移的次数不会超过 $B$ 次。 小并到大的，直接扫一遍小的往大的里塞。 大并到小的，和上面同理。但我们无需新开一个 $id$，直接 $id_b\gets id_a$ 继承一下就可以。 小的和小的在一起，我们需要讨论一下。如果新出来的集合大小是 $\geq B$ 的，我们需要新开一个 $id$。否则直接合并。 代码和上面一样的。 # 完整代码 [AT submission 47747560](https://atcoder.jp/contests/abc329/submissions/47747560) 代码里前半段注释是本题正常的 STL 做法，感兴趣的也可以学习一下。