[技巧] 当你使用「整体二分」就可以对强连通分量「动态维护」？！

· · 算法·理论

文章名称还是学的五人组（\text{Badcen，Melor，Kamuamua，Unclered，Heimao}，现在已经实质进入解散状态）的风格。

考虑如下问题：有一个图，初始时只有 n 个顶点。现在按照顺序往图内加入 m 条有向边，要求求出每次操作后图中强连通分量的数量。

这个问题要求我们对强连通分量“在线”维护，但这显然是无法做到的，因此我们考虑用某些离线算法求出答案。可以看出，本题中离线比在线的优势在于可以对一些数据进行预处理，因此我们容易有一个想法，即使用分治法求解，先对时间戳较小的边进行处理，然后把这些边的影响一起统计，最后递归进时间戳较大的一边进行子问题处理。这个思路实质上和整体二分一致。

具体地，我们考虑当前求解 [L, R] 时间戳内的边。令 mid = \lfloor \frac{L + R}{2} \rfloor，则我们先拉出时间戳在 [l, mid] 中的边和对应的所有点跑一遍 \text{tarjan} 或者其他求解强连通分量的算法。对于求出的每个强连通分量，它们在 (mid, R] 的时间内一定还保持着强连通性（因为只加边，不删边）。而对于一对此时不能互相到达的节点，它们在 [L, mid] 中的任意时间一定也不能互相到达。

则我们把当前的边划分为两个集合：时间戳不大于 mid 且两端在我们求解出的同一个强连通分量的归为 \text{A} 类边，否则归为 \text{B} 类边。我们递归求解 [l, mid] 的子问题并只保留 \text{A} 类边（容易看出 \text{B} 类边对 [l, mid] 的答案无影响），再把我们刚才求解出的强连通分量用并查集缩点，最后递归 (mid, R] 并只保留 \text{B} 类边。

我们分析一下复杂度：每条边在每一层只会向 [l, mid] 或者 (mid, R] 中的一侧递归，而 \text{tarjan} 遍历的点数与边数成正比关系，因此边的总遍历次数为 O(n \log n) 级别，至此我们可以用整体二分“动态维护”强连通分量了。

P5163 和 CF1989F 都是这个技巧的运用。前者需要加上权值线段树合并维护强连通分量中的价值集合，后者需要我们先对问题进行简单的转化和图论建模，再用上面的方法求解。