一、题目
点此看题
二、解法
只能说是精神污染了,虽然每个部分都不难把但是放在一起就很难写了。
考虑无向图的情况是好做的,我们直接离线逆序询问,那么删边操作就变成了加边,单点增加操作就变成了单点减少。那么做法是显然的,我们线段树合并维护加边操作,再支持线段树单点修改和线段树上二分即可。
本题是强连通分量怎么办呢?我们类比无向图的情况,还是先离线逆序询问,考虑把每一条边的效果等效为合并两个强连通块。那么我们求出每一条边有用的时间 \(f\),也就是恰好在这个时刻这条边的两个端点在同一个强连通分量里。
发现这个时刻是单调的,而我们要对所有边都求出这样一个时刻,那么可以考虑整体二分。考虑现在要判断一条边的 \(f\) 和 \(mid\) 的大小关系,那么我们保留加入时间在 \([0,mid]\) 的边(为 \(0\) 就表示没有被删除),如果这条边的加入时间 \(\leq mid\) 并且两端点在同一强连通分量中,那么它的 \(f\leq mid\),否则 \(f>mid\)
但是这样做时间复杂度又有点不对,我们可以考虑动态 \(\tt tarjan\),也就是假设我们已经对保留 \([0,l)\) 边的图缩过点了,那么我们再此基础上加入 \([l,mid]\) 的边就可以了。所以我们整体二分的时候先走右边再走左边,走右边的时候把新加入的边也保留,然后使用可撤销并查集就可以维护缩点的结果。
时间复杂度 \(O(n\log^2 n)\),复杂度瓶颈在可撤销并查集。
#include
#include
#include
#include
#include
#include