傻逼 ds
gym103687K. Dynamic Reachability
首先看到这个巨大的时限 \(12\operatorname{s}\) ，盲猜一手是 \(bitset\) 或者是分块结果两个都有
最直观的想法肯定是直接搜，复杂度是 \(O((n+m)q)\) 的，不可以接受，但是这种做法太没有拓展性了，考虑一些有拓展性的做法，发现一般图传递闭包是 \(O(\frac{n^3}{\omega})\)，但是拓扑图的传递闭包是 \(O(\frac{nm}{\omega})\) ，考虑把他缩点成一个拓扑图然后拓扑排序，时间复杂度 \(O((n+m+\frac{nm}{\omega})q)\) 更加不能接受了，但是这个看起来就比上面那个高级很多，因为我们能求出整张图上每个点能到达的所有点，这个是上面做不到的，而且每次修改只会改一条边，所以图不会产生太大的变化
这时候就感觉应该是分块了，我们把每 \(B\) 个询问放到一块做，设这 \(B\) 个操作里面涉及到的点为关键点，涉及到的边为关键边，发现我们就是问关键点的连通性，我们对于每个点维护一个关键点的 \(bitset\) ，表示这个点能到达的关键点，通过黑色的非关键边跑拓扑排序求出，这样就在不考虑关键边的情况下建出了不含关键边的关键点新图，因为我 \(bitset\) 只维护关键点，所以复杂度就是 \(O(\frac{mB}{\omega}q)\)
先不管关键边，思考怎么查询，直观想法是继续拓扑排序，但是这样没有拓展性，因为我不可能建出新图后递归上面那坨答辩算法，因为万一是我建出来的就是拓扑图就寄了不能递归了，所以考虑一开始就提出的 \(bfs\) ，发现现在的图很小了，只有 \(B\) 个点 \(B^2\) 条边，直接跑复杂度是 \(O((B+B^2)q)\) 的。
现在来分析一下复杂度，将上面的答辩加起来是 \(O(\frac{q}{B}(n+m+\frac{mB}{\omega})+(B+B^2)q)\) ，化简一下是 \(O(\frac{mq}{\omega}+\frac{q}{B}(n+m)+B^2q)\)，根号平衡一下 \(B\) 发现大概是 \((n+m)^{\frac{1}{3}}\) ，然后就结束了……吗？
算一下复杂度大概是 \(6e8\) 左右，然后我们就开心的写，然后就 \(T\) 了 
发现有一个神奇的东西，用 \(bitset\) 优化 \(bfs\) 可以做到 \(O(n+\frac{n^2}{\omega})\) ，现在复杂度就是 \(O(\frac{mq}{\omega}+\frac{q}{B}(n+m)+\frac{B^2}{\omega}q)\) 了，复杂度大概是 \(2.5e8\) ，我也不知道，反正就是能过了