题解：P11775 [COTS 2013] 集合合并 / RAZGOVORI

Monomial · 2025-04-18 10:46:17 · 题解

初始有一个上界为 \lceil \log n \rceil + 1 次，下界为 \lceil \log n \rceil 次的做法：我们考虑直接用线段树的形式进行合并，每层余下来的一个扔出来最后用已经成为全集的合并，容易证明扔出来的个数 \leq \frac{n}{2}，那么这些都可以有一个匹配的来合并。

然后考虑如何对一些情况将上限优化到 \lceil \log n \rceil 次。容易发现 n 为奇数（无法砍半）和 n=2^{k} （已经到下界）的情况无法再去优化，只能对 n=t \times 2^{k} 的情况优化，其中 t 为奇数。

我们把整个序列分成 t 段，每段长度 2^{k}，先在段内用 k 次合并，然后再把每个段砍半，分成前部和后部，我们每次用一个段的后部对位匹配另一个段的前部即可。

接下来利用倍增的思路，我们要求每次操作后一个集合包含了连续 2^{i} 个段的信息，可以直接往后找第一个没有合并的位置，次数为 \lceil \log t \rceil，这个时间复杂度 \mathcal{O}(n^2)，空间 \mathcal{O}(\frac{n^2}{\omega}+ n \log n) ，或者精细实现一下，时空复杂度 \mathcal{O}(n \log n)。

upd on 2025.07.22:

前面有很多胡言乱语，提供一下更好写的方法。

实际上，我们可以对于 2 \mid n 的情况，按长度为 2 分块。每次用上面的方法倍增做匹配。而对于 2 \nmid n 的情况，我们可以取最大的 k 使得 2^k \leq n，然后先把后面 n-2^k 个在前面每个找对应匹配一下，接下来对 2^k 个做倍增，最后再把最后的 n-2^k 个补成全集。

这样可以少写很多东西，时间复杂度还是 \mathcal{O}(n \log n)。