题解

思路

设城市格 $c$ 的海拔为 $h$。一台泵能够抽干 $c$，当且仅当泵所在格与 $c$ 在“只保留海拔不超过 $h$ 的格子”后属于同一个四连通分量。因为水位降到 $h$ 时，这条路径上的地面都不会阻断连通；反之，任何海拔高于 $h$ 的格子都会形成无法越过的地面屏障。

按城市海拔从低到高考虑。若某个城市格所在的当前低地分量已经含泵，就无需新增；否则任何可抽干它的泵都必须落在这个分量中，因此至少要新放一台。放置后给该分量作标记。随着阈值升高，分量只会合并，泵标记取逻辑或即可。

同一海拔的全部格子必须先激活并完成合并，再处理这一海拔的城市格，否则会把同一水平面上的连通区域错误拆开。

做法

子任务 1：一维区间搜索

一维地图至多有 $1000$ 个格子。按城市海拔排序；对每个城市格，向左右扩展经过所有海拔不超过当前海拔的格子，得到它的完整低地连通区间。若区间内没有既有泵，就在当前格放一台。

子任务 2：单一城市海拔

设全部城市格海拔均为 $H$。只保留海拔不超过 $H$ 的格子，做一次四连通分量搜索；答案就是含城市格的连通分量个数。

子任务 3：批量激活并查集

按海拔从低到高激活所有格子。激活一个格子时与已经激活的四邻格合并，并把“该分量是否已有泵”的标记一并合并。处理完同一海拔的全部格子后，再枚举该海拔的城市格；若所在分量没有泵，就令答案加一并标记该分量。

海拔只在 $0$ 到 $1000$ 之间，可以用桶代替比较排序。

复杂度

• 子任务 1：时间 $O((mn)^2)$，空间 $O(mn)$。
• 子任务 2：时间 $O(mn)$，空间 $O(mn)$。
• 子任务 3：时间 $O(mn\alpha(mn))$，空间 $O(mn)$。

正确性证明

对每个海拔阈值 $h$，已激活格子的并查集分量恰好是海拔不超过 $h$ 的四连通分量，这是由逐点激活和四邻合并直接得到的。

按城市海拔归纳。处理海拔 $h$ 的城市格时，较低城市所需的泵已按最少数量放置并随分量合并保留。若当前分量已有泵，该泵可经不高于 $h$ 的路径抽干当前城市格；若没有泵，则任何能抽干该格的泵都必须位于同一分量，所以所有可行方案都至少要为该分量增加一台泵。算法恰好增加一台，因此每一步保持最优，最终答案最小。