APIO2019 桥梁

Day \(\mathbb{Z}(\text{Ni})\)。

想成 kruskal 重构树后就再也不会了。

考虑没有修改怎么做，将所有边和询问按照权值从大到小排序，对于一个询问 \((s,w)\)，向并查集中插入所有边权 \(\ge w\) 的边，维护连通块大小即可。

现在有了修改，考虑对询问修改分块。设每 \(B\) 个询问修改重构一次并查集，每次仍然将（前面块的修改后的）边权和询问从大到小排序，然后顺序加边，如果一条边被当前块内修改就跳过。

询问 \((s,w)\) 时枚举块内每个修改 \((e_i=(u,v),w')\)，如果修改时间在查询时间之前并且 \(w'\ge w\) 并且是这个询问之前的最后一次修改，向并查集中加入边 \((u,v)\)；如果修改时间在查询时间之后并且 \((u,v)\) 本来的边权 \(\ge w\)，也向并查集中加入 \((u,v)\)。每次询问之后撤销贡献即可。

复杂度是 \(O(\frac{q}{B}(m\log m+B^2\log n))\) 的。