震惊，某退役菜鸡为了写水题的更优解法居然做出这件事！

WeLikeStudying · 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)，最终代码。