题目简述

给定一个 ( N \times N ) 的网格，每个格子有不同的高度。
定义一个 山谷 为：

1. 区域：4 连通（上下左右）的一块格子。
2. 无洞：该区域的补集（包括网格外的无限高区域）在 8 连通意义下是连通的。
3. 边界条件：区域内所有格子的高度严格小于其边界上任意格子的高度。

求所有山谷的 大小之和。

---

核心难点

1. 无洞的判断：在网格图上，如何高效判断一个 4 连通区域是否包含洞？
2. 边界条件：如何保证区域内格子的高度都小于边界格子高度？
3. 规模：( N \leq 750 )，需要 ( O(N^2 \log N) ) 或 ( O(N^2 \alpha(N)) ) 的算法。

---

关键思路

1. 按高度升序处理

因为高度互不相同，我们可以将格子按高度从小到大排序。
当我们处理到某个格子时，所有高度小于它的格子都已经被加入考虑。
这样，当前格子所在的连通块 的边界格子（4 邻接且不在块内）的高度一定大于块内所有格子高度（因为边界格子还没被加入）。

因此，按高度顺序构造的连通块天然满足边界高度条件。

---

2. 无洞的判定（欧拉公式）

在平面网格图中，对于一个 4 连通的区域，可以用 欧拉特征 判断是否有洞：

定义：

• ( V ) = 区域内的格子数（顶点数）
• ( E ) = 区域内相邻格子之间的边数（4 连通边）
• ( F ) = 区域内完整的 ( 2 \times 2 ) 方块数

对于平面图，欧拉公式为： [ V - E + F = C + H ] 其中：

• ( C ) = 连通分量数（这里 ( C = 1 )）
• ( H ) = 洞的数量

因此：

• 如果 ( V - E + F = 1 ) → 无洞
• 如果 ( V - E + F > 1 ) → 有洞（多一个洞，值加 1）

---

3. 并查集维护连通块

我们维护每个连通块的：

• ( V )：块内格子数
• ( E )：块内边数
• ( F )：块内 ( 2 \times 2 ) 方块数

初始加入一个格子时：

• ( V = 1 )
• ( E = 0 )
• ( F = 0 )

---

4. 合并时的更新

当两个连通块合并时：

• ( V_{\text{new}} = V_1 + V_2 )
• ( E_{\text{new}} = E_1 + E_2 + \text{新增的边数} )
• ( F_{\text{new}} = F_1 + F_2 + \text{新增的方块数} )

新增的边数：检查两个块之间相邻的格子对，每对在合并后成为内部边。

新增的方块数：检查所有包含新内部边的 ( 2 \times 2 ) 方块，如果该方块的 4 个格子都在合并后的块内，则新增一个方块。

---

5. 算法流程

1. 将所有格子按高度升序排序。
2. 初始化并查集，每个元素记录 ( V, E, F )。
3. 依次加入每个格子：
   • 设置该格子为已激活。
   • 初始化该格子的 ( V=1, E=0, F=0 )。
   • 检查 4 个方向的邻居，若已激活，则合并连通块。
   • 更新合并后连通块的 ( E ) 和 ( F )（新增的边和方块）。
4. 对于合并后的连通块（根节点），检查：
   • 若 ( V - E + F = 1 )（无洞），则该块是一个山谷，将 ( V ) 加入答案。
5. 输出答案。

---

复杂度分析

• 排序：( O(N^2 \log N) )
• 并查集操作：( O(N^2 \alpha(N)) )
• 每次合并时更新 ( E ) 和 ( F ) 是 ( O(1) )，因为只需检查常数个相邻边和方块。

---

例子验证

以样例为例，按高度从小到大处理，每当形成一个无洞连通块时，累加其大小，最终得到 30。

---

总结

这道题的关键在于：

1. 利用高度排序保证边界条件自动满足。
2. 利用欧拉公式 ( V - E + F ) 判断洞的存在。
3. 使用并查集动态维护连通块信息，并在合并时更新 ( E ) 和 ( F )。

这样就能在 ( O(N^2 \log N) ) 时间内求出所有山谷大小之和。