题意

有 $N$ 个点，给定 $M$ 条有正整数边权的无向边。$Q$ 次询问，每次给定 $l, r$，选出一些边使得所有点都与 $[l, r]$ 中的某一点连通，求最小边权和。

数据范围：$2 \leq N \leq 10^5$，$1 \leq M \leq 10^5$，$1 \leq Q \leq 2 \times 10^5$。

题解

问题相当于 $[l, r]$ 内的点已连通，求最小生成树。容易转化为：在原图最小生成树上，找到区间 $[l, r]$ 中的任意两点之间路径上边权最大，去重后得到正好 $r - l$ 条边，答案即为总边权减去这些边的边权和。

在 Kruskal 重构树上考虑这个问题，相当于 $[l, r]$ 中的这 $r - l + 1$ 个叶子结点之间的所有 LCA。对于每个结点考虑它的贡献，相当于将两个儿子结点中的编号排序放到一起考虑，每个编号用所在子树作为类型标记，编号序列中，只要区间包含不同类型，这个结点就会作为 LCA 产生贡献。

区间包含关系可以转化为分别对两个端点的限制，即二维偏序问题。而一个结点处产生的矩形修改操作数不超过两个子树中大小较小值的两倍，根据启发式合并复杂度分析，至多有 $\mathcal{O}(n \log n)$ 次矩形修改操作。同样，每个结点可以使用启发式合并的方式维护一个 std::set 表示字树内的所有编号。

总时间复杂度为 $\mathcal{O}(n \log^2 n + q \log n)$。