题解：P8164 [JOI 2022 Final] 沙堡 2 (Sandcastle 2)

惊为天人的做法，来自 _YangZj。

如何判断一个矩形是否存在如题所述的哈密顿路径？我们首先站在最大值的位置上，每次走向相邻的位置中，比自己小的最大者，若相邻的位置都大于当前所在的位置则停止，检查是否遍历整个矩形即可。

这启示我们把每个位置向它相邻的位置中比自己小的最大者连边，我们会得到一个森林，我们需要检查它是否是一条链。

设 a_i 为点 i 在原矩阵中的值，f_i 为 i 的父亲在原矩阵中的值，若 i 为根则 f_i=0。点分成两类：

1. 对于一个四周都小于它的位置（可能成为起点的位置），我们对它赋权 X-f_i，其中 X 是一个足够大的值；
2. 否则对它赋权 a_i-f_i。

首先所有点的点权 >0，因为我们的连边保证 a_i>f_i，且 X 足够大。并且显然森林中至少有一个 1 类点，该点到根的路径上的点权之和为 X。

所以这个森林为一条链当且仅当这样赋权后所有点权之和为 X。

所以我们枚举矩形的上下边界，对于每个右端点可以 O(1) 统计有多少左端点合法。

#include<unordered_map>
#include<iostream>

const int N = 233, M = 5e4, X = 1e9;
int n, m, a[N][M];
long long s, sm, l[N][M], c[N][M], r[N][M];
std::unordered_map<long long, int>ct;
int inline f(int x, std::initializer_list<int>il) {
    int s = X, mx = 0;
    for (int y : il) y < x ? mx = std::max(mx, y) : s = x;
    return s - mx;
}
int main() {
    if (int i, j; std::cin >> n >> m, n < m) for (i=0; i<n; i++)
        for (j=0; j<m; j++) std::cin >> a[i][j];
    else for (std::swap(n, m), i=0; i<m; i++)
        for (j=0; j<n; j++) std::cin >> a[j][i];
    for (int i=1, j; i<n-1; i++) {
        for (j=0; j<m-1; j++) l[i][j] = l[i-1][j] + f(a[i][j], {a[i-1][j], a[i][j+1], a[i+1][j]});
        for (j=1; j<m; j++) r[i][j] = r[i-1][j] + f(a[i][j], {a[i-1][j], a[i][j-1], a[i+1][j]});
        for (j=1; j<m-1; j++) c[i][j] = c[i-1][j] + f(a[i][j], {a[i-1][j], a[i][j-1], a[i+1][j], a[i][j+1]});
    }
    for (int i=0, j, k; i<n; i++) for (j=i+1; j<n; j++, ct.clear()) for (k=s=1; k<m; k++) {
        ct[l[i][k-1] - l[j-1][k-1] - f(a[i][k-1], {a[i+1][k-1], a[i][k]}) - f(a[j][k-1], {a[j-1][k-1], a[j][k]}) + s]++;
        auto it = ct.find(s + f(a[i][k], {a[i+1][k], a[i][k-1]}) + f(a[j][k], {a[j-1][k], a[j][k-1]}) + r[j-1][k] - r[i][k] - X);
        if (it != ct.end()) sm += it->second;
        s += c[j-1][k] - c[i][k] + f(a[i][k], {a[i+1][k], a[i][k-1], a[i][k+1]}) + f(a[j][k], {a[j-1][k], a[j][k-1], a[j][k+1]});
    }
    for (int i=0, j, x, y; i<n; i++) for (j=1, x=y=0; j<m; sm+=x+y, j++) if (a[i][j] < a[i][j-1]) x++, y = 0; else y++, x = 0;
    for (int j=0, i, x, y; j<m; j++) for (i=1, x=y=0; i<n; sm+=x+y, i++) if (a[i][j] < a[i-1][j]) x++, y = 0; else y++, x = 0;
    std::cout << sm + n * m;
}

点评：这我哪会啊