U368446 P9715 (QFOI T4)

说明：本题提供 P9715 的两组 hack 数据，分别针对普通并查集写法和 std 写法（类并查集链表），数据生成器见附件. 构造方法是在序列上建出二项树结构，不断查最深的叶子. 建树完成后，所有偶数次查询的复杂度均为 $\Theta(\log n)$. 该构造方法与普通路径压缩并查集的卡法相同，可以用相同的方式避免（增加按秩合并，优化至 $\Theta(\alpha(n))$）. 然而，在实际的数据下，这样做（可能）会由于更大的常数得到更慢的结果. 由于并查集的常数实在太小（以及本数据的有效规模只到 $2^{18}=524288$，笔者比较懒不想写非 $2^k$ 的数据生成器），并不能卡掉 std 的带 $\log$ 做法. 可以通过在代码里添加 `cnt` 统计每次询问的循环次数来验证数据的正确性. --- 二项树是使路径压缩并查集达到最坏复杂度的经典构造，本题的意义在于证明，这样的结构在简单得多的序列上也是可以构造出来的.（也说明并查集的常数是真的小……相比之下同为带 $\log$ 的 `set` 做法简直不能看.） 尽管如此，并查集（或类并查集链表）维护仍然是本题的优秀做法（码量极小、跑得飞快），而且在 OI 中并不少见. 因此，本题仍然是一道好题.

无

无

无