题意理解

我们有一个 $n \times m$ 的网格图（经纬度），每个点是一个国家，边是道路：

• 横向边：$(i,j)$ 与 $(i,j+1)$ 相连，并且第 $m$ 列与第 $1$ 列相连（环形）
• 纵向边：$(i,j)$ 与 $(i+1,j)$ 相连（但 $n$ 与 $1$ 不相连）

每条边有一个安保代价（权重）。

每个询问 $[l_i, r_i]$ 表示：经度在 $[l_i, r_i]$ 之间的国家处于战争，不能使用。我们要在剩下的和平国家之间，选择一些和平道路（两端都是和平国家），使得和平国家连通，并且总安保代价最小。

---

核心难点

1. 图非常大：$m$ 最多 $10^9$（测试点4），$n$ 最多 $100$，不能直接存储整个图。
2. 环形结构：横向是环，战争区间会破坏环的连续性。
3. 多次询问：需要高效处理每个询问。
4. 边权随机生成：不能依赖特殊权重结构。

---

解题思路

关键观察

和平国家 = 所有国家去掉 $[l_i, r_i]$ 列。
由于 $n$ 较小（≤100），我们可以把地图看作 $n$ 行 $m$ 列的网格，按列处理。

---

问题转化

删除 $[l_i, r_i]$ 列后，剩下的是前后两个连续区间的列（因为环形，删除一段连续区间后，剩下的是两段连续区间）。

设删除区间 $[l, r]$，那么和平区域是：

• 左段：列 $[1, l-1]$
• 右段：列 $[r+1, m]$

我们要在这些列对应的点上求 MST。

---

预处理列区间MST信息

由于 $n$ 很小，我们可以预处理每个列区间的 MST 相关信息。

定义 $L[i]$ 表示从第 $1$ 列到第 $i$ 列这些列的 MST 信息（不仅仅是权重和，还要记录与右边界相连的边信息，因为合并区间时需要）。

同样定义 $R[i]$ 表示从第 $i$ 列到第 $m$ 列这些列的 MST 信息。

---

合并两个区间

对于询问 $[l, r]$，和平区域是左段 $[1, l-1]$ 和右段 $[r+1, m]$。

我们已知：

• $L[l-1]$ 包含列 $1..l-1$ 的 MST 信息
• $R[r+1]$ 包含列 $r+1..m$ 的 MST 信息

现在要把这两个区间合并成一个连通图（因为左右两段在环上是相邻的，它们之间在第 $1$ 列与第 $m$ 列有横向边连接）。

---

区间MST信息的表示

我们不可能存整个 MST（太大），但可以存：

• 该区间的 MST 权重和
• 该区间最左列的每个节点在 MST 中的连通分量编号
• 该区间最右列的每个节点在 MST 中的连通分量编号
• 以及这些连通分量之间的边（用于合并时）

实际上，由于 $n$ 很小，我们可以用最小生成树的关键边思想：当合并两个区间时，只需要考虑两个区间相邻边界列之间的横向边，以及两个区间各自内部的连通情况。

---

做法：Kruskal 重构树 / 并查集合并

我们可以预处理：

1. 对每个前缀 $[1,i]$ 计算 MST，并记录：

   • 总权值 $sumL[i]$
   • 最右列（第 $i$ 列）的 $n$ 个节点在 MST 中的连通块编号（映射到 $1..n$）
   • 这些连通块之间的最小边权（用于与右区间合并时）

2. 对每个后缀 $[i,m]$ 类似处理，得到 $sumR[i]$ 和最左列连通信息。

3. 对于询问 $[l,r]$：

   • 左区间 $[1,l-1]$ 的 MST 权值和 = $sumL[l-1]$
   • 右区间 $[r+1,m]$ 的 MST 权值和 = $sumR[r+1]$
   • 但直接相加会重复计算一些边（因为左右两段在列 1 与列 m 处有环边连接），需要合并。

---

合并左右区间

左右区间合并时，新增的边是：

• 第 $l-1$ 列与第 $l$ 列之间的横向边（但第 $l$ 列是战争列，不能用）
• 实际上，左右区间在环上相邻的边是：第 $1$ 列与第 $m$ 列之间的横向边（因为环形）

所以合并时，我们加入第 $1$ 列与第 $m$ 列之间的 $n$ 条横向边，用 Kruskal 方法合并左右区间的连通块。

---

实现方法

我们预处理：

• $pre[i]$：列 $[1..i]$ 的 MST 信息（权和 + 右边界连通性）
• $suf[i]$：列 $[i..m]$ 的 MST 信息（权和 + 左边界连通性）

对每个询问：

1. 取 $pre[l-1]$ 和 $suf[r+1]$
2. 将它们的 MST 权和相加
3. 加入第 $1$ 列与第 $m$ 列之间的 $n$ 条边（边权由输入生成器确定）
4. 在这些边 + 左右区间边界信息上做 Kruskal，得到合并后的 MST 权和

---

复杂度

• 预处理 $O(n m \log n)$（$m$ 大时不能直接做，需要优化）
• 每个询问 $O(n \log n)$ 合并

对于 $m$ 很大的情况，不能真的预处理每个前缀/后缀，需要用线段树维护区间 MST 信息，支持区间合并。

---

关键数据结构

我们可以用线段树，每个节点 $[l,r]$ 存储：

• 该区间的 MST 权和
• 左边界列（第 $l$ 列）的连通信息
• 右边界列（第 $r$ 列）的连通信息

合并两个相邻区间时，只需在中间加入两区间相邻列之间的 $n$ 条横向边，做一次 Kruskal。

这样预处理 $O(m n \log n \log m)$，查询 $O(n \log n)$。

---

总结

这道题的核心是：

1. 将环形区间删除转化为两个连续区间的合并
2. 利用 $n$ 小的特点，用边界列的连通性表示区间 MST 信息
3. 用线段树维护区间 MST，支持快速合并
4. 询问时合并左右两段，并加入环形连接边，求最终 MST

这样就能在 $n$ 小 $m$ 大的情况下高效处理多次询问。