题解：P9531 [JOISC2022] 复兴计划
liangbowen
·
·
题解
blog。提供一份代码短的题解。
一个暴力做法：维护 w_i<w_{now} 与 w_i\ge w_{now} 的前后缀 MST，查 X_i 时将前后缀 MST 合并，直接求得答案。
考虑一棵 (u_{now},v_{now},W) 的前缀 MST。因为 w_i<W 时 w_i 越大 |W-w_i| 越小，所以枚举所有 w_i<W，按边权从大到小加边：
- 先忽略掉 (u_{now},v_{now}) 的边。
- 对于其他 w_i<W，尝试加入。如果成功加入并且构成了包含 (u_{now},v_{now}) 的环，显然需要删除最大边，加入最小边。显然最大边就是 w_i，最小边就是 w_{now}，删掉 i 并加入 now。
找到这个 i。那么 w_{now} 对答案有贡献，当且仅当询问的 X 有 X-w_i> w_{now}-X，即 X>\dfrac{w_i+w_{now}}2。
同理，w_i 在 X>\dfrac{w_i+w_{now}}2 时会结束贡献。那么每条边都会有一个贡献区间，可以加入 MST 当且仅当在贡献区间内。
用并查集模拟上述算法，找出贡献区间 [l_i,r_i]，那么对于不同的 X，边 i 的贡献为：
写个指针状物，因为询问的 X_i 有序，顺着扫一遍即可。可以看代码理解。
code，时间复杂度 O(nm+q\log m)。
写了 1.5k，其实应该可以写进 1k 的（