P5163 WD与地图 与 NH20220928D 联通 以及若干感想

gzw2005 · 2022-09-29 08:51:40 · 个人记录

背景： 一年前写过的 P5163 WD与地图，在模拟赛 T4 还是这道题的 原题弱化版 的情况下居然没有想出来而被薄纱。故特此记录这道题的思维过程，希望 gzw2005 以后不要再犯这种无可饶恕的漏洞了。

• NH20220928D 联通题意：给定一个 n 个点的图，一开始没有任何边，现对于时刻 [1,m]，每单位时刻加入一条有向边 (u_i,v_i)。给定 q 个询问，问 (x_i,y_i) 在同一强连通分量内的最早时刻。n,m,q\le 2\times10^5.

显然在持续加边的情况下，这个在同一分量的时刻是满足单调性的，不会并在一起后又分开。因此，我们可以试图二分每个询问的最早时刻。

又因为这里是 q 组询问，所以可以使用 整体二分 来平衡外层二分和 Check 的复杂度。

但是这样并不好做，因为我们无法直接知道每个分量要在什么时候被缩在一起。

一条有向边，只有在它的两个端点被缩进同一个强连通分量里才能发挥作用，否则加进去也没用。因此，我们需要知道 每条边的端点被缩进同一分量 的时间。那这倒也没什么大的改变，只是也要将每一条边当成询问放进整体二分里罢了。

简单设计下整体二分的框架。假设现在答案已缩小至 [L,R]：

• 将当前边集中出现时间 \le mid 的边加入当前图，> mid 的边不管，因为肯定合并时间 > mid。然后跑一次 Tarjan。
• 对于每个询问，对于所有出现时间 \le mid 的 边 / 询问 检查是否被缩进同一个强连通分量里，如果是则分进 [L,mid]，否则分进 [mid+1,R]。
• 往两边继续递归，直至 L=R.

但是一次 Tarjan 的缩点是 O(n+m) 的。我们发现我们只需要对加入的边 涉及到的点 跑一次 Tarjan 即可。这样时间复杂度变为 O(m)。

至于如何 维护 / 检查 是否在同一强连通分量里，这个处理的方式不同会导致不同的复杂度：

• 全局的(可撤销)并查集：我们使用一个并查集维护当前的强连通分量。在加入完出现时间 \le mid 的边之后，我们 立即 往 [mid+1,R] 进行递归，这样就可以使用之前的强连通信息，右半部分结束后，我们将这次 Tarjan 缩的点撤销，然后再往左半部分 [L,mid] 递归。由于要撤销，时间复杂度要多个 \log n。

• 重新标号：我们发现其实目的都是为了让每条边的端点找到其所在分量的编号。我们跑完 Tarjan 之后可以得到一个 \texttt{belong[]} 数组，将 要往右半部分递归 的 边 / 询问 \texttt{(u,v)} 直接修改为 \texttt{(belong[u],belong[v])}。然后再往下跑。此时因为重新标号了，Tarjan 复杂度仍然是与边数同阶。单次时间复杂度直接变为 O(m)。

综上时间复杂度为 O(n\log^2 n) 或 O(n\log n)。（视 n,m,q 同阶）

• P5163 WD与地图题意：给定一个 n 个点 m 条边的有向图，现有 q 次操作和询问，删除一条有向边 (u_i,v_i)，或询问 p_i 所在强连通分量的第 k_i 大元素。n,m,q\le 2\times10^5.

考虑时间倒流，变成加边操作。然后仍然是我们先像上一题那样可以预处理每条边被缩在一起的时间。然后就变成了线段树合并模板题。

感想

WD 与地图 已经是一道历史悠久的题目了，高一时候的我望着这道题的题解，但却搞不懂「只需要对边数涉及的点跑塔扬」究竟是怎么一回事，然后似懂非懂地敲下了代码，这个疑问延续至今。直至在模拟赛被薄纱，我想这也是不认真思考的最终命运。

虽然在现在看来这个技巧可以说是这么生动显然，但这也说明了自己一个很难堪的问题，自己要为不认真的过去买单。思维的完备性十分重要。如果之前自己智力低下无法理解无可厚非，但是如果现在都不赶紧把之前轻易留下的漏洞修补，那么我觉得 gzw2005 本可以不用抱无用的幻想，可以直接退役。

自己还没搞懂的题目和结论究竟有哪些，自己心知肚明。毕竟不希望自己的 OI 是一个充满疑惑的 OI。

简而言之，我只想告诉 gzw2005，不要得过且过。