题解：P12736 [POI 2016 R2] 圣诞灯链 Christmas chain

· · 题解

十分有趣的题。

思路

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

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

有一种比较无脑的方式，注意到有效合并最多 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