本题有没有离线线性的做法？

P3367 【模板】并查集

critnos @ 2021-02-27 11:19:51

RT，我现在想到的貌似是用线性树上并查集每次新建一个节点把 x 和 y 的祖先合并到这个节点上，然后对于询问操作用标准 RMQ 欧拉序 lca 或者线性树上并查集 tarjan lca 判断 lca 的被合并到的时间？

by JRzyh @ 2021-02-27 11:35:03

路径压缩并查集不是 O(m\alpha(n)) 的吗？

by RBI_GL @ 2021-02-27 11:36:41

路径压缩的合并操作可以看做常数复杂度吧）

by JRzyh @ 2021-02-27 11:36:58

还是说lz需要 O(n) 而不是 O(m) ?

by critnos @ 2021-02-27 11:38:49

等等欸这里没法使用线性树上并查集

by tommy0221 @ 2021-02-27 11:40:57

@Zhaoyuhang2008 单路径压缩不是 O(n\alpha(n)) 的，是 O(n\log n) 的，你还得带启发式合并才是 O(n\alpha(n)) 的。

by critnos @ 2021-02-27 11:42:27

@Zhaoyuhang2008 @hy236_zxh 指正。。姚期智的论文证明了路径压缩在平均复杂度下是 \alpha(n) 的。。事实上同时使用路径压缩和按秩合并才是最坏 \alpha(n) 的

by critnos @ 2021-02-27 11:43:33

我 sb 了，，我现在想到的那个是假的

by Autofreeze @ 2021-02-27 11:44:01

@Zhaoyuhang2008 只路径压缩只是随机 O(n \alpha(n))

by critnos @ 2021-02-27 11:52:19

@Zhaoyuhang2008 O(n+m) 罢

by 1saunoya @ 2021-02-27 11:52:37

@mcyl35

你在说你 * 呢直接路径压缩就好了又不是复杂度很垃圾

| 下一页