自动搬运

查看原文

来自洛谷，原作者为

	Monomial ?

搬运于2025-08-24 23:10:09，当前版本为作者最后更新于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)$。