【开摆计划 #1】WD与地图

WeLikeStudying · 2022-09-09 15:12:29 · 题解

• 本题为开摆计划 T8。
• 本题有一个理论复杂度优于目前正解 O(n\log) 的做法，不需要使用可撤销并查集，由于本题强制时光倒流，强行套线段树合并的做法不够接近本质，重写一遍旧的代码，仍然显得冗长无趣，作者，以及该做法的发现者，均不愿意给出原题做法的代码实现，故只给出方法指导在此，请见谅。
• 下面是作者以前写的 O(n\log^2) 做法。

题意

• 给一个有向图，支持删边，单点修改，求单点所在强连通分量中前 k 大节点的权值和。

分析

• 时光倒流改成加边，但是加边维护强连通分量是什么。
• 尝试用一个更简单的描述：只要我们知道加入的一条边在什么时候被缩进强连通分量里了，我们就可以用线段树合并高效地支持合并操作与修改操作，但是这玩意怎么求呢？
• 单个二分很好求，多个尝试整体二分？
• 对于多个分段的操作，我们可以尝试分段加边，前一段加的边可以直接转化为连通性，为我们整体二分提供了条件。
• 可以这样，对于确认答案在区间 [l,r] 内的节点，将出现时间不超过区间中点的边加入，用 \text{Tarjan} 缩点（为了保证复杂度只遍历有边的点）然后用可撤销并查集合并连通块，然后先求解右儿子，撤销连通块之后求解左儿子，复杂度 O(n\log^2n)。

代码实现

• 实现可撤销并查集注意事项：
• 记得初始化 size，代码。
• 实现 Tarjan 注意事项：
• 保证复杂度需要不访问孤立点，代码。
• 实现权值线段树合并注意事项：
• 查询的时候一个点有相同值要特判，代码。
• 代码实现。