P2391 白雪皑皑 题解

原题链接：P2391。

并查集好题。

首先我们知道，并查集在一个无向图中可以维护两点之间的连通性，判断条件为：\(find(u)==find(v)\)。而对于这道题来说，我们可以用并查集来维护一个序列区间的重叠性或者说区间的连通性。因为题目上说了后面的操作会覆盖前面的操作，所以我们可以考虑倒序进行操作，这样先操作的点之后就一定不会再被覆盖了。

那如何用并查集来维护呢，我们可以设 \(fa_{i}\) 表示在 \(i\) 之前的第一个还没有被操作的点，而这种关系是可传递的，即 \(fa_{i}=fa_{fa_{i}}\)，于是就可以用并查集维护了。