#include<bits/stdc++.h> #define N 2520 usingnamespacestd;
template <typename T> inlinevoidread(T &num){ T x = 0, f = 1; char ch = getchar(); for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') f = -1; for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ '0'); num = x * f; }
int n, m, a[N][N], stk[N], cnt, top, ans; vector<int> ok[N][N]; //ok[l][r]: a[l][i]~a[r][i]为合法段的i的集合 pair<int, int> tmp[N]; //临时存答案 int lok[N][N], rok[N][N];
voidsolve(int *num, int len){ //找出所有合法段 cnt = top = 0; for (int i = 1; i <= len; i++) { while (top && num[i] > num[stk[top]]) { if (i > stk[top] + 1) tmp[++cnt] = make_pair(stk[top]+1, i-1); //num[l] < num[r] top--; } if (top) { if (i > stk[top] + 1) tmp[++cnt] = make_pair(stk[top]+1, i-1); //num[l]>num[r] if (num[i] == num[stk[top]]) top--; //特殊处理相等情况 } stk[++top] = i; } }
voidcalc(int l, int r, int u, int d){ //左右边界为l,r;上下边界在[u,d]内 int len = 0; for (int i = u - 1; i <= d + 1; i++) { a[0][++len] = a[i][r]; } solve(a[0], len); //找出列的合法段 for (int i = 1; i <= cnt; i++) { int tl = tmp[i].first + u - 2, tr = tmp[i].second + u - 2; if (lok[tl][tr] <= l) ans++; } }
intmain(){ read(n); read(m); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { read(a[i][j]); } } for (int i = 2; i < n; i++) { //预处理ok集合 solve(a[i], m); for (int j = 1; j <= cnt; j++) ok[tmp[j].first][tmp[j].second].push_back(i); } for (int r = 2; r < m; r++) { //枚举矩形右边界 for (int i = 1; i <= n; i++) a[0][i] = a[i][r]; solve(a[0], n); for (int i = 1; i <= cnt; i++) { if (rok[tmp[i].first][tmp[i].second] + 1 < r) lok[tmp[i].first][tmp[i].second] = r; rok[tmp[i].first][tmp[i].second] = r; //lok[u][d]表示只考虑列的限制,当矩形的上下边界为u,d,右边界为r时,左边界最左是哪里 } for (int l = 2; l <= r; l++) { //枚举矩形左边界 if (!ok[l][r].size()) continue; int lst = ok[l][r][0]; for (int i = 1; i < ok[l][r].size(); i++) { if (ok[l][r][i] > ok[l][r][i-1] + 1) { //找出ok[l][r]中的一个连续段 calc(l, r, lst, ok[l][r][i-1]); lst = ok[l][r][i]; } } calc(l, r, lst, ok[l][r][ok[l][r].size()-1]); } } printf("%d\n", ans); return0; }