题目解析 这道题要求统计所有满足条件的"山谷"区域大小之和。山谷的定义是：

连续的区域（四连通）

不含洞（八连通的补集）

区域内所有格子的高度都低于边界格子的高度

核心思路 关键观察 将格子按高度从小到大处理，这样可以保证：

当处理到某个格子时，所有高度比它小的格子已经被加入

当前格子加入后，可能形成新的山谷或扩大现有山谷

算法流程 预处理：将所有格子按高度排序

增量构建：从低到高依次加入格子

连通性维护：使用并查集维护当前已加入格子的连通块

洞检测：通过计算边界格子数量来判断是否有洞

洞检测原理 对于每个连通块，维护 v[F] 表示：

初始值为 -1（表示当前格子自身）

每有一个相邻的已加入格子，v[F] 加 1

对于每个完整的 2×2 方块（四个格子都已加入），v[F] 减 1

关键性质：当 v[F] == -1 时，该连通块是一个山谷

代码详解 cpp // 按高度排序所有格子 sort(nd + 1, nd + n * n + 1);

for (int h = 1; h <= n * n; ++h) { ci x = nd[h].x, y = nd[h].y; in[x][y] = 1; // 标记该格子已加入

// 与相邻的已加入格子合并
for (int d = 0; d < 4; ++d) {
    ci xx = x + fx[d], yy = y + fy[d];
    if (in[xx][yy])
        merge(fd(id[x][y]), fd(id[xx][yy]));
}

ci F = fd(id[x][y]);

// 统计边界格子（相邻的已加入格子）
for (int d = 0; d < 4; ++d) {
    ci xx = x + fx[d], yy = y + fy[d];
    if (in[xx][yy])
        ++v[F];
}

// 检测2×2方块，调整洞计数
for (int i = -1; i <= 0; ++i)
    for (int j = -1; j <= 0; ++j) {
        bool ok = 1;
        for (int a = 0; a <= 1; ++a)
            for (int b = 0; b <= 1; ++b)
                ok &= in[x + i + a][y + j + b];
        if (ok)
            --v[F];
    }

// 如果v[F] == -1，说明这是一个山谷
if (v[F] == -1)
    ans += siz[F];

} 时间复杂度 排序：$O(N^2 \log N)$

并查集操作：近似 $O(N^2 \alpha(N^2))$

总体：$O(N^2 \log N)$

样例验证 对于样例：

text 1 10 2 20 100 30
3 11 50 算法按高度顺序处理格子，正确识别出所有8个山谷，大小分别为1,1,1,2,3,6,7,9，总和为30。

这种方法巧妙地利用了高度排序和并查集，高效地解决了复杂的几何连通性问题。