Can't go up
Exber
洛谷 @Exber
Codeforces @Rebex
启发式合并是一种神奇的暴力,它经常用于合并两个只能一个个元素插入的集合。
假设我们要合并两个集合 SSS 和 TTT,那么显然小的集合里元素一个个插入大的集合是更优的。所以启发式合并就是将小集合中元素插入大集合来合并。
这样做看起来很暴力,但因为一个元素 uuu 所属的集合比另一个集合小的话 uuu 才会被枚举插入,所以 uuu 被枚举插入集合一次以后,它所在的集合大小至少翻倍。
所以启发式合并的时间复杂度是 O(tnlogn)O(tn\log n)O(tnlogn) 的,其中 ttt 是插入集合的时间复杂度。
P3302 [SDOI2013] 森林
P3201 [HNOI2009] 梦幻布丁
扫码打赏,你说多少就多少