启发式合并学习笔记

启发式合并是一种神奇的暴力，它经常用于合并两个只能一个个元素插入的集合。

假设我们要合并两个集合 $S$ 和 $T$，那么显然小的集合里元素一个个插入大的集合是更优的。所以启发式合并就是将小集合中元素插入大集合来合并。

这样做看起来很暴力，但因为一个元素 $u$ 所属的集合比另一个集合小的话 $u$ 才会被枚举插入，所以 $u$ 被枚举插入集合一次以后，它所在的集合大小至少翻倍。

所以启发式合并的时间复杂度是 $O(tn\log n)$ 的，其中 $t$ 是插入集合的时间复杂度。

练习题目

• P3302 [SDOI2013] 森林

• P3201 [HNOI2009] 梦幻布丁