P2391 白雪皑皑——经典并查集

· · 个人记录

并查集这块真的经典吗......只是看好多博客有提到过

其实不算很难，但是如果正向考虑想不到并查集

不过有一个思考就是题目中给出的两个式子具有周期性，循环周期为 n

利用这个应该可以数据结构暴力碾过去

正解

正向思考发现模拟会爆炸

考虑反过来

发现对于覆盖问题来说，只看最后覆盖的部分

也就是说如果倒着枚举，只要染上颜色就被确定了，不可能再被更改

那么每个点至多会被染色一次

当模拟遍历的时候如果碰到了已经染色的点，直接跳到最右侧没有被染色的点

这个时候就可以把一片已经染色的区间并为一个集合，共享一个右端点

时间复杂度 O(m+n\alpha(n))

关于集合

集合是什么呢

从集合的一种表示来看

就是一类具有性质的对象的总体

那么当我们的对象具有相同性质时，它们就可以并到一个集合里

如果加上大部分都是合并，就可以想到并查集