[题解] LuoguP5443 [APIO2019]桥梁
2021-01-04 21:27
标签：lin 没有 rac com line code inline 怎么 一段 https://www.luogu.com.cn/problem/P5443 有一个显然的暴力，对于一个询问直接枚举\(m\)条边，如果边权\(\ge w\)就在并查集中合并。 如果没有修改的话还可以将操作离线，排序后不断向并查集中加边。 注意到有些边并不会被修改，得到一个不怎么暴力的暴力 将没有被修改的边单独拉出来，同时将所有询问以及这些边按\(w\)从大到小排序，像上面那样对于一个询问不断向并查集中加入这类边。 对于会被修改的边，暴力算这条边现在的边权，判断是否会被加入并查集。 处理完一个询问后撤销第二类边即可。 需要可撤销并查集，并不能路径压缩，可以启发式合并，一次合并变成\(\log n\) 粗略的估计一下复杂度为\(O(Q \log Q+m \log m + Q^2 \log n)\) 发现这样我们暴力了所有可能会被修改的边，考虑过一段时间将边权都存下来。 即对操作分块，令每\(B\)个操作为一块。 对一个块，保存好在这之前所有边的边权。 然后块内的修改以及查询做上述暴力。 复杂度\(O(\frac{Q}{B}(B \log B + m \log m + B^2 \log n))\) 大概是\(O(Q \log B + \frac{Qm \log m}{B} + QB \log n)\) 取\(B = \sqrt{m \log m}\)，\(1000\)左右的样子 然后注意卡卡常（ https://paste.ubuntu.com/p/2XzGvrmNfR/ [题解] LuoguP5443 [APIO2019]桥梁 标签：lin 没有 rac com line code inline 怎么 一段 原文地址：https://www.cnblogs.com/wxq1229/p/13192769.htmlSolution
答案就是\(s\)所在连通块的大小。对于修改，直接更改边的权值即可。真就人傻常数大呗Code
文章标题：[题解] LuoguP5443 [APIO2019]桥梁
文章链接：http://soscw.com/index.php/essay/40110.html