Just Green Enough (USACO Silver 2021 February)

500x500的矩阵，每个数1..200，求最小值正好为100的子矩形的数量。

不用区间查询线段树的情况下，因为 $N$ 比较小，我们可以考虑 $\mathcal{O}(N^3)$ 的算法：

固定住 $y_{min}$ 和 $y_{max}$ ，我们要数有多少个合适的 $x_{min}$ 和 $x_{max}$ 。
我们统计在 $y_{min}$ 和 $y_{max}$ 范围内的每一列的最小值 $gmin[x]$ ，这个直接滚动计算就可以了。
得到 $gmin[]$ 后，我们用two-pointer从左向右扫描， $l$ 指向上一个 $\lt 100$ 值的位置， $r$ 指向上一个 $100$ 的位置，然后区间 $(l,r]$ （左开右闭）到当前位置 $x$ 的所有子矩阵都是可以的。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n;
int g[505][505];
int gmin[505];
ll ans;
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            scanf("%d", &g[i][j]);
    for (int y1 = 0; y1 < n; y1++) {
        for (int x = 0; x < n; x++) gmin[x] = 200;
        for (int y2 = y1; y2 < n; y2++) {
            for (int x = 0; x < n; x++) gmin[x] = min(gmin[x], g[y2][x]);
            int l = -1;                    // 上一个 <100
            int r = -1;                    // 上一个 100
            for (int x = 0; x < n; x++) {  // 双指针扫描
                if (gmin[x] < 100) l = x;
                if (gmin[x] == 100) r = x;
                if (r > l) ans += r - l;
            }
        }
    }
    printf("%lld\n", ans);
    return 0;
}