自动搬运

查看原文

来自洛谷，原作者为

	WeLikeStudying 

搬运于2025-08-24 22:07:49，当前版本为作者最后更新于2022-09-30 19:51:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

• 我十分惭愧，在此感谢奆佬，祝愿其信息学之路光芒璀璨。
• 另外还有我们机房同志们的帮助，参照了此篇博客，在此一并感谢。
• 前情提要。
• 本题将简述复杂度 $O(m\log m+q\log (n+q))$ 的做法，优于目前所有题解的复杂度，实现只需要 $2.9\text{KB}$，是不折不扣的小清新做法。
• 原博客写太糊了吗？那我重新改一点，这只是一个优化时间复杂度和代码复杂度的平凡小 trick 啊，我估计绝大多数人肯定早就发现了，至于写这么多吗。
• 本题题解经过改版之后已经比题解区绝大多数题解详细了，而且加了更优的做法，代码也更简短，应该能过了吧。
• 作者已经退役，希望这篇题解能够帮到更多的人。

题意

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

套路转化

• 题目很不接近本质！所以作者要像洋葱一样一层层拨开，这些外皮其它博客已有讲述，在此没有详细实现，可以参照前情提要。
• 一道好题不应该是两道题拼在一起，一道好题会有自己的idea —— 而它应该不加过多包装地突出这个idea。
• 套路 1：加边比删边（一般）更容易，所以时光倒流改成只有加边的情况。
• 套路 2：考虑弱化问题，对于无向图的情况，我们可以用线段树合并在（不离散化 $O(q\log w)$，离散化 $O(q\log(n+q))$）的时间和空间复杂度内维护整个信息。
• 套路 3：转化成弱化问题，对于每条有向边，如果能算出它什么时候被缩入一个强连通分量内，即可转化为无向图的情况。
• 套路 4：观察特殊性质，对于单条边，答案满足可二分性，对于多条边的情况，我们可以尝试整体二分。

整体二分里的细节（传统做法）

• 我们扒拉一下整体二分里发生了什么！
• 已知答案在 $[l,r]$ 区间内，我们要判断一些边有没有被缩入强连通分量内部，把出现时间 $\le mid$ 的边加入，注意缩点的时候要不考虑孤立点以保证复杂度，把被缩入的边和不被缩入的边分成左右两部分。
• 这个时候，左边的边可以直接下传 $[l,mid]$（左儿子），而 $[mid+1,r]$（右儿子）的边要体现左端点贡献的强连通性，不难发现可以用并查集表示这种强连通性，因此，最传统的方法简述如下：

（传统做法）方法简述

• 建图，把出现时间 $\le mid$ 的边加入缩好强连通性的图中。
• 跑 Tarjan 来缩点，为了保证复杂度，不要遍历孤立点。
• 根据强连通性把边划为两个部分。
• 把新产生的强连通性加入并查集。
• 求解右儿子。
• 将本层产生的强连通性从并查集中撤回。
• 求解左儿子。
• 显然，每一层如果处理 $m$ 条边，由按秩合并的可撤销并查集所产生的复杂度不超过 $O(m\log m)$，而每条边最多经过 $\log$ 层，复杂度为 $O(m\log^2m)$，代码。
• 这也是为什么我之前说整体二分的复杂度是瓶颈，而我们为什么可以优化呢？原因很简单！

为啥如此简单的小 trick 要让作者讲这么久

• 实际上，体现强连通性的方法很简单：只需要把被缩起来的点当成同一个点就好了。
• 这题的做法看似没有优化空间，仔细观察还是可以发现我们要维护的东西具有比并查集弱的性质：如果一些点被缩起来之后，我们只需要取一个根来代替它，如果这个根再被缩起来，我们不需要考虑这个根代表的其它点了！这便是诀窍！
• 我们在 Tarjan 的时候，便可以给所有点选出一个代表，然后对于下传到右儿子的边，把点替换为其代表即可。

（新做法）方法简述

• 建图，把出现时间 $\le mid$ 的边加入缩好强连通性的图中。
• 跑 Tarjan 来缩点，为了保证复杂度，不要遍历孤立点，为每一个强连通分量内的点选出一个代表。
• 根据强连通性把边划为两个部分。
• 用代表把要加入右儿子内部的边重标号。
• 求解左儿子。
• 求解右儿子。
• 显然，该做法不需要并查集，每一层如果处理 $m$ 条边，由 Tarjan 所产生的复杂度不超过 $O(m)$，而每条边最多经过 $\log$ 层，复杂度为 $O(m\log m)$，最终代码。