https://gmoj.net/senior/#main/show/6525
若没有洞的限制，答案显然从每个点出发的极大联通块（联通块的每个点高度小于等于起点高度）的大小和。
那么将高度排序，从小到大用并查集维护即可。
现在要看有没有洞，考虑平面图欧拉公式：
(V+F=E+2)，其中(V)是点数，(F)是块数，(E)是边数，则(F=E+2-V)。
这里把每个格子定义为点，若相邻格子都属于当前并查集，则它们之间有边。
不难发现(F=1（外面的大块）+相邻四个（小正方形）都属于当前并查集的个数+洞的个数)
所以要动态地维护点数、边数、小正方形个数。
若直接套用启发式合并，时间复杂度：(O(n^2~log~n^2*大常数))，卡一卡能过。
仔细思考，发现每次是合并一个格子P和周围4个格子（高度小于(h[P])）。
如果(P)周围的两个格子属于不同的并查集，那么它们的并查集的点之间是没有四相邻的，不然就已经被合并了。
所以新产生的边和小正方形都包含(P)，那么就暴力扫一扫(P)的周围就好了，时间复杂度(O(n^2~α))。
Code ：
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define fo(i, x, y) for(int i = x, _b = y; i <= _b; i ++)
#define ff(i, x, y) for(int i = x, _b = y; i < _b; i ++)
#define fd(i, x, y) for(int i = x, _b = y; i >= _b; i --)
#define ll long long
#define pp printf
#define hh pp("
")
using namespace std;
const int N = 755;
int n, a[N][N];
#define pii pair<int, int>
#define fs first
#define se second
pii b[N * N]; int b0;
int cmpb(pii x, pii y) {
return a[x.fs][x.se] < a[y.fs][y.se];
}
int id[N][N];
int mov[8][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
int f[N * N], e[N * N], g[N * N], siz[N * N];
int F(int x) { return f[x] == x ? x : (f[x] = F(f[x]));}
void bin(int x, int y) {
if(F(x) != F(y)) {
x = f[x], y = f[y];
siz[y] += siz[x];
e[y] += e[x];
g[y] += g[x];
f[x] = f[y];
}
}
int qv(int x, int y, int w) { return F(id[x][y]) == w;}
int calc_e(int x, int y, int w) {
int s = 0;
fo(j, 0, 3) s += qv(x + mov[j][0], y + mov[j][1], w);
return s;
}
int calc_g(int x, int y, int w) {
int s = 0;
s += qv(x - 1, y - 1, w) && qv(x - 1, y, w) && qv(x, y - 1, w);
s += qv(x - 1, y, w) && qv(x - 1, y + 1, w) && qv(x, y + 1, w);
s += qv(x, y + 1, w) && qv(x + 1, y, w) && qv(x + 1, y + 1, w);
s += qv(x, y - 1, w) && qv(x + 1, y - 1, w) && qv(x + 1, y, w);
return s;
}
int main() {
freopen("valleys.in", "r", stdin);
freopen("valleys.out", "w", stdout);
scanf("%d", &n);
fo(i, 1, n) fo(j, 1, n) {
scanf("%d", &a[i][j]);
b[++ b0] = pii(i, j);
id[i][j] = (i - 1) * n + j;
}
sort(b + 1, b + b0 + 1, cmpb);
fo(i, 1, n * n) f[i] = i, siz[i] = 1;
ll ans = 0;
fo(i, 1, b0) {
int x = b[i].fs, y = b[i].se;
fo(j, 0, 3) {
int u = x + mov[j][0], v = y + mov[j][1];
if(u && v && u <= n && v <= n) {
if(a[u][v] < a[x][y]) {
bin(id[u][v], id[x][y]);
}
}
}
int w = F(id[x][y]);
e[w] += calc_e(x, y, w);
g[w] += calc_g(x, y, w);
if(e[w] + 2 - siz[w] - g[w] == 1)
ans += siz[w];
}
pp("%lld
", ans);
}