Luogu5163 WD与地图

题意：给出一张有向图，支持下列操作:

• 删除一条边

• 将 的点权增加

• 求 所在强连通分量中，前 大的点权和

允许离线，，，时限 。

---

出处是一个杜老师题。

删边维护 SCC，一脸不可做，考虑时光倒流变成加边。

仍然不好直接做，考虑求出每条边被“缩起来”的时间。

如果能求出这个，维护强连通性就和无向图连通性一样简单了……线段树合并就能解决。

---

发现“缩起来”是具有单调性的，可考虑整体二分。

朴素的判定：将出现时间 的边全部建立，然后缩点。此时若某条边两端在同一个强连通分量内，则其被缩起来的时间 。

（边既是修改，也是询问）

整体二分处理分治区间 的流程如下：

• （边 已经在图中）

• 将边 加入图中并缩点

• 对于每条边，判断它是否已经被缩起来了。若是，丢进 继续二分，否则丢进 继续二分。

• 处理子问题 。

• 将边 从图中删除。

• 处理子问题

每次暴力缩点复杂度显然不对。

整体二分能节约复杂度，重点在于它能配合数据结构，快速“继承” 的“影响”。若将边 简单存储，每次询问时缩点，相当于没有维护。

考虑这样的做法：继承边 缩点的结果，此时会出现若干 SCC，这形成一种连通关系，可以用可撤销并查集维护和集成。不在 SCC 内部的边是 DAG 边，我们缩点时只需要考虑 DAG 边。

留下的 DAG 边仍可能很多，复杂度似乎仍然不对。但观察可以发现，在处理分治区间 时：

• 将 中能缩起来的边丢进子问题
• 将 中未缩起来的边丢进子问题

我们发现，需要询问的边正是那些余下的 DAG 边！基于这个巧合，DAG 边的总考虑次数就仅是 的。

---

处理分治区间 的具体流程：

• 把 的边加入缩好 SCC 的图中。

• 跑 tarjan 来缩点，为了保证复杂度为 而非 ，不要遍历没有边相连的点。

• 将新产生的强联通性加入并查集。

• 对于每条边，判断它是否已经被缩起来了。若是，丢进 继续二分，否则丢进 继续二分。

• 处理子问题 。

• 撤回并查集操作，使得强连通性回到 的情形。

• 处理子问题 。

复杂度 。