并查集是一个森林，每棵树表示一个集合，并且这个集合根据某种具有传递性的关系构建起来。 普通并查集关心的信息只有 $x$ 所在集合的根，$fa_x$ 表示的仅仅是一个传递性关系，即 $fa_x$ 与 $x$ 所在集合的根相同。从任意节点往上跳，都能找到它所在集合的根。 使用路径压缩优化，在向上访问节点时，把路径上所有节点的 $fa$ 都改为根，那么就…

满足「结合律」的静态信息 CF1175E Minimal Segment Cover 预处理 $rt_x$ 表示点 $x$ 经过一条线段能到达的最右边的点。 跳区间显然是满足结合律的，可以倍增之，复杂度 $O(n \log_2 n)$。 这类题目有一个重要的小技巧：为了满足最优性，倍增时跳到不能到达 $y$ 的最远的点 $p$，然后判断能一次跳过 …