自动搬运

查看原文

来自洛谷，原作者为

	kkxacj Full of Hope.

搬运于2025-08-24 23:17:49，当前版本为作者最后更新于2025-07-15 15:04:56，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

十分有趣的题。

思路

容易发现，每次操作就是让你将一些点连边，使其赋上一样的颜色。

这个很容易用并查集维护，不过每次是告知一段区间相同，考虑如何优化。

有一种比较无脑的方式，注意到有效合并最多 $n-1$ 次，然后考虑启发式合并，每次把连通块小的那些点颜色全部赋为连通块大的颜色，然后考虑哈希看区间是否相同，用树状数组维护即可，然后每次二分找到第一个不相同的地方，复杂度 $\operatorname{O}\left(n\log^2n\right)$。

我们并不满足这个复杂度，我们考虑 ST 表的思想，将区间表示为两个长度为 $2^k$ 的区间的并集，由于是看两边相等所以可以重复，我们只需要对于每一层维护一个并查集即可。

这样的话，我们又可以在最后把 $2^k$ 转成两个 $2^{k-1}$，复杂度 $\operatorname{O}\left(n\log n \times \alpha \left(n\right)\right)$，复杂度优化十分显著，从大于十秒到不到一秒。

code