blog。提供一份代码短的题解。
一个暴力做法：维护 \(w_i<w_{now}\) 与 \(w_i\ge w_{now}\) 的前后缀 MST，查 \(X_i\) 时将前后缀 MST 合并，直接求得答案。
考虑一棵 \((u_{now},v_{now},X)\) 的前缀 MST。因为 \(w_i<X\) 时 \(w_i\) 越大 \(\mid X-w_i\mid\) 越小，所以按边权从大到小加边：
- 先加上 \((u_{now},v_{now})\) 的边。
- 如果 \(w_i\ge X\)，不管他。
- 如果 \(w_i<X\)，尝试加入。如果成功加入并且构成了包含 \((u_{now},v_{now})\) 的环，说明 \((u_i,v_i)\) 的加入构成了一个环。
code，时间复杂度 \(O(nm+q\log m)\)。
写了 1.5k，其实应该可以写进 1k 的（
标签：1.5,code,题解,复杂度,now,P9531 From： https://www.cnblogs.com/liangbowen/p/18312848