题解：道路网整备 2（最小维修成本连通问题）

核心结论：通过并查集维护初始连通性，将查询转化为“区间覆盖”问题，用贪心+倍增预处理快速计算最小维修成本，判断能否让所有查询点连通。

一、核心思路（通俗版）

1. 问题本质：要让多个交叉点连通，可维修部分行的东西向道路（整行解锁封锁路段），需找到“总成本最低”的维修方案，或判断无法连通。
2. 关键观察：
   • 初始连通性：未维修时，交叉点通过已有通行道路（A/B为1的路段）形成连通分量。
   • 维修的作用：维修第i行后，该行所有东西向道路解锁，能极大扩展连通范围。
   • 成本优化：优先维修成本C_i=1的行（贪心），最小化总天数。
3. 问题转化：查询的交叉点分属不同初始连通分量，需找到最少成本的维修行，让这些连通分量的“行范围”覆盖成一个连续区间，且纵向道路能连通这些行。

二、关键预处理（O(N log N + H×W)）

1. 并查集维护初始连通性

• 两个并查集：
  • 网格并查集（fa数组）：维护交叉点的连通关系，合并有通行道路（A/B为1）的相邻交叉点。
  • 行并查集（ff数组）：维护行与行的连通关系，仅当纵向道路（B为1）连通两行时合并。
• 每个连通分量记录：左右边界行（lef/ rig数组），即该分量覆盖的最小行号和最大行号。

2. 贪心相关预处理

• pr数组：记录每个行i能“自然覆盖”到的最大行号（无需维修的连通范围）。
• v数组：行i的实际覆盖范围（max(i, pr[i])），保证单调不减。
• las数组：记录每行i左侧最近的“成本1维修行”（C_i=1的行），优先用低成本维修。

3. 倍增数组（加速查询）

• 构建两个倍增数组f[0][i][l]和f[1][i][l]，分别表示“从行i出发，走2^l步低成本维修”能覆盖到的最大行号，快速跳跃计算覆盖范围。

三、查询处理（O(T log N + log N) per query）

1. 第一步：检查初始连通性

• 所有查询点通过网格并查集找根节点，去重后若只剩1个根，说明已连通，输出0。

2. 第二步：提取连通分量的行范围

• 每个根节点对应一个行范围[lef[p], rig[p]]，收集所有查询点的行范围，去重排序后简化为“核心行范围列表”（rel数组）。

3. 第三步：判断纵向连通性

• 若核心行范围的最上行和最下行不在同一行并查集，说明纵向道路无法连通，输出-1。

4. 第四步：计算最小维修成本

• 贪心策略：优先用成本1的维修行，通过倍增数组快速跳跃，计算覆盖所有核心行范围所需的最少维修次数（成本总和=维修次数，因优先选C_i=1）。
• 若跳跃后能覆盖所有核心行范围，输出维修次数；否则输出-1。

四、代码核心逻辑解释

• 网格并查集：合并相邻通行的交叉点，记录每个连通分量的行范围。
• 行并查集：判断不同行能否通过纵向道路连通，是连通的前提。
• 倍增数组：避免暴力遍历维修行，用2^l步跳跃快速计算覆盖范围，降低查询复杂度。
• 贪心选择：优先选C_i=1的行，保证总成本最小，这是解题的关键优化。

五、复杂度分析

• 预处理：网格并查集O(H×W)，倍增数组O(N log N)，总复杂度O(H×W + N log N)，适配H×W≤1e6的限制。
• 查询：每个查询处理O(T log T)（去重排序）+ O(log N)（倍增跳跃），总复杂度O(ΣT log T + Q log N)，适配Q≤1e5、ΣT≤2e5的限制。

六、总结

这道题的核心是“连通性转化+贪心+倍增加速”：先将交叉点连通转化为行范围覆盖，再用贪心选低成本维修行，最后用倍增快速计算所需维修次数。关键是抓住“优先成本1维修”和“行范围覆盖”两个核心，通过预处理降低查询压力。