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

P3367 【模板】并查集

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

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

by critnos @ 2021-02-27 11:53:28

@Isaunoya 我是想问有没有 O(n+m) 的啊

by critnos @ 2021-02-27 11:54:17

答非所问？不解

by Seauy @ 2021-02-27 11:55:18

@mcyl35 胡错了

by 1saunoya @ 2021-02-27 11:57:50

@mcyl35

那行 我好好回答一下你的问题…

首先你的 RMQ欧拉序 预处理竟然是线性的……教一下吗

然后你的 tarjanLCA 竟然可以不用并查集…求教

建议学四毛子 学完四毛子之后解决你的 lca 一切问题（

by critnos @ 2021-02-27 11:58:45

@Isaunoya

  1. 我当然知道有 O(n)-O(1) rmq

  2. https://ljt12138.blog.uoj.ac/blog/4874

by Seauy @ 2021-02-27 11:59:06

@Isaunoya 好像RMQ确实可以线性的

by 1saunoya @ 2021-02-27 12:03:39

@Seauy 草 你就是RMQ建笛卡尔树然后四毛子的老哥？

by JRzyh @ 2021-02-27 12:04:58

@Isaunoya 建议别喷

但其实这科技真的没用。

by critnos @ 2021-02-27 12:33:14

看起来没人回了/kk

说句闲话，还有一个想法

把边的插入时间记录下来作为边权，然后问题就转化为了求两点之间的一条路径使得路径上的边权最大值 \le 这个询问的时间。

然后跑 tarjan 的期望线性 mst，就把图简化为了一棵树。

但是树上两点之间的最大值也不会线性做法，有神仙能给个做法吗/kk

上一页 |