5163

更好的阅读体验 P5163 WD与地图 喵喵题，但其实没有那么难。 删边倒序转成加边是显然的，询问可以通过值域线段树合并实现，修改，合并，查询都是好做的。考虑如何维护动态加边的 SCC。 难点是每个时刻缩点后的图是一个 DAG，并不像无向图的搜索树一样好维护，而且新加入的边可能不会立刻构成 SCC ......

来一发分治题解吧。 感觉和单纯的整体二分还是有一点区别。 虽然整体二分也能看作分治就是了。 思路 首先时光倒流。 删边改为加边。 这没有什么好说的，比较基础。 我们考虑在不断加边时，每两个点是在什么时候变成一个强连通分量里面的。 考虑分治。 首先在 \([l,r]\) 内选取中点 \(\text{m ......

Day \(\lfloor\pi^3\rfloor\)。 原神答辩缝合怪题目。 先考虑无向图的版本怎么做。套路地，考虑时间倒流，然后就变成了加边、改点权、查询连通块前 \(k\) 大之和，线段树合并加并查集维护即可。 现在的边有向，依旧考虑时间倒流，相当于将连通块改成了强连通分量。问题在于只有一条边 ......