---

题目分析

我们有一个 $n \times m$ 的网格，每个格子有高度 $a[i][j]$。
要求统计所有矩形区域的数量，满足：

1. 矩形不能触及边界（即 $1 \le r_1 \le r_2 \le n-2, 1 \le c_1 \le c_2 \le m-2$）。
2. 对于矩形内的每个格子 $(i,j)$，它必须严格小于：
   • 左边相邻列同一行的格子 $(i, c_1-1)$
   • 右边相邻列同一行的格子 $(i, c_2+1)$
   • 上边相邻行同一列的格子 $(r_1-1, j)$
   • 下边相邻行同一列的格子 $(r_2+1, j)$

换句话说，矩形内部每个格子都比它所在行左右边界外的格子和所在列上下边界外的格子都要低。

---

关键观察

如果我们固定一个格子 $(i,j)$，它可能在多个矩形中。
对于它在某个矩形内是合法的，必须同时满足：

1. 它比它左边一列的格子 $(i, j-1)$ 更高吗？不，不是左边一列，而是矩形的左边界列 $c_1-1$，这取决于矩形范围。
2. 类似地，它比它右边一列的格子 $(i, j+1)$ 高吗？不，是和 $c_2+1$ 比较。

但是注意：矩形的边界 $c_1, c_2$ 是固定的，所以对于格子 $(i,j)$：

• 它必须比 $(i, c_1-1)$ 小，即 $a[i][j] < a[i][c_1-1]$
• 它必须比 $(i, c_2+1)$ 小，即 $a[i][j] < a[i][c_2+1]$

对列也是类似：

• $a[i][j] < a[r_1-1][j]$
• $a[i][j] < a[r_2+1][j]$

因此，对于每个格子 $(i,j)$，我们可以预处理四个方向上的“合法边界”：

---

预处理思路

定义：

• left[i][j]：从 $(i,j)$ 向左看，离它最近的大于等于它的列位置（不包括自己），即最大的 $c < j$ 使得 $a[i][c] \ge a[i][j]$，如果没有则记为 $-1$。
• right[i][j]：从 $(i,j)$ 向右看，离它最近的大于等于它的列位置（不包括自己），即最小的 $c > j$ 使得 $a[i][c] \ge a[i][j]$，如果没有则记为 $m$。
• up[i][j]：从 $(i,j)$ 向上看，离它最近的大于等于它的行位置，即最大的 $r < i$ 使得 $a[r][j] \ge a[i][j]$，如果没有则记为 $-1$。
• down[i][j]：从 $(i,j)$ 向下看，离它最近的大于等于它的行位置，即最小的 $r > i$ 使得 $a[r][j] \ge a[i][j]$，如果没有则记为 $n$。

这样，当矩形左边界在 $c_1$ 时，要求 $c_1-1 > left[i][j]$（即 $c_1 \ge left[i][j]+2$），否则 $(i,j)$ 不合法。
当矩形右边界在 $c_2$ 时，要求 $c_2+1 < right[i][j]$（即 $c_2 \le right[i][j]-2$）。

类似地，对于行边界 $r_1, r_2$，要求 $r_1-1 > up[i][j]$（即 $r_1 \ge up[i][j]+2$），$r_2+1 < down[i][j]$（即 $r_2 \le down[i][j]-2$）。

---

问题转化

对于每个格子 $(i,j)$，它对矩形 $(r_1,r_2,c_1,c_2)$ 合法的条件是：

• $r_1 \le i \le r_2$
• $c_1 \le j \le c_2$
• $r_1 \ge up[i][j] + 2$ （记 U = up[i][j] + 2）
• $r_2 \le down[i][j] - 2$ （记 D = down[i][j] - 2）
• $c_1 \ge left[i][j] + 2$ （记 L = left[i][j] + 2）
• $c_2 \le right[i][j] - 2$ （记 R = right[i][j] - 2）

并且矩形本身不能碰边界：$r_1 \ge 1, r_2 \le n-2, c_1 \ge 1, c_2 \le m-2$。

因此，$(i,j)$ 能存在于矩形中，当且仅当区间 $[U, i]$ 和 $[i, D]$ 非空，且区间 $[L, j]$ 和 $[j, R]$ 非空，并且矩形边界在有效范围内。

---

统计方法

我们枚举矩形的上边界 $r_1$ 和下边界 $r_2$（$1 \le r_1 \le r_2 \le n-2$），然后看在这个行范围内，有哪些列区间 $[c_1, c_2]$ 是合法的。

对于固定 $r_1, r_2$，我们要找 $1 \le c_1 \le c_2 \le m-2$，使得对于所有 $i \in [r_1, r_2]$ 和 $j \in [c_1, c_2]$，都有：

• $r_1 \ge up[i][j] + 2$
• $r_2 \le down[i][j] - 2$
• $c_1 \ge left[i][j] + 2$
• $c_2 \le right[i][j] - 2$

也就是说，对于每个格子 $(i,j)$，它给出了对 $c_1$ 的下界限制和对 $c_2$ 的上界限制。并且这个限制对 $i$ 在 $[r_1, r_2]$ 内都要满足。

---

列限制的合并

对于固定的 $r_1,r_2$ 和列 $j$，我们看第 $j$ 列在行区间 $[r_1, r_2]$ 内的格子。
要求对于这些格子中的每一个，都有 $c_1 \ge left[i][j]+2$ 且 $c_2 \le right[i][j]-2$。

因此，对于列 $j$，定义：

• colL[r1][r2][j] = 行区间 $[r_1, r_2]$ 内第 $j$ 列所有格子的 left[i][j]+2 的最大值。
• colR[r1][r2][j] = 行区间 $[r_1, r_2]$ 内第 $j$ 列所有格子的 right[i][j]-2 的最小值。

如果对于某个 $j$，colL > colR，那么这一列不可能出现在任何合法矩形中（自身矛盾）。

---

最终统计

对于固定 $r_1, r_2$，我们得到了每个列 $j$ 的限制区间 $[colL[j], colR[j]]$，要求 $c_1 \ge colL[j]$ 且 $c_2 \le colR[j]$ 对所有 $j \in [c_1, c_2]$ 成立。

因此，对于矩形列区间 $[c_1, c_2]$ 合法，必须满足：

• $c_1 \ge \max_{j \in [c_1, c_2]} colL[j]$
• $c_2 \le \min_{j \in [c_1, c_2]} colR[j]$

这是一个经典的区间合法性计数问题，可以用单调栈或双指针来做。

---

时间复杂度优化

直接枚举 $r_1, r_2$ 再枚举列区间是 $O(n^2 m^2)$ 的，太大。

我们可以用以下优化：

1. 预处理 left, right, up, down：用单调栈，$O(nm)$。

2. 枚举 $r_1$ 时，逐步增加 $r_2$，并维护 colL[j] 和 colR[j] 的当前值（取 max/min 更新）。

3. 对于当前 $r_1, r_2$，我们要计算列区间的数量，满足：

   • 对区间内所有 $j$，$c_1 \ge colL[j]$ 且 $c_2 \le colR[j]$。

   可以换个角度：对于每个 $c_1$，求最大的 $c_2$ 使得条件成立。
   即要求 $c_2 \le \min_{j \in [c_1, c_2]} colR[j]$，并且 $c_1 \ge \max_{j \in [c_1, c_2]} colL[j]$。

   可以用双指针：

   • 固定 $c_1$，让 $c_2$ 向右扩展，同时维护区间内 colL 的最大值 maxL 和 colR 的最小值 minR。
   • 当 c1 < maxL 或 c2 > minR 时停止扩展。
   • 如果扩展停止时满足 $c_1 \le c_2$ 且 $c_1 \ge 1, c_2 \le m-2$ 且 $c_1 \ge maxL, c_2 \le minR$，则这是一个合法列区间。
   • 注意：当 $c_1$ 增加时，maxL 和 minR 可以更新，可以用两个单调队列维护滑动窗口最大值/最小值。

这样对于固定 $r_1, r_2$，统计列区间是 $O(m)$ 的。

总复杂度：$O(n^2 m)$。

---

---

复杂度分析

• 预处理：$O(nm)$
• 主循环：$O(n^2 m)$
  对于 $n,m \le 2500$，$n^2 m$ 最大约 $1.56 \times 10^{10}$，显然会超时，需要进一步优化。在实际竞赛中，本题可能有更优的 $O(nm)$ 或 $O(nm \log n)$ 解法，但这里给出的是直观的思路框架。对于满分需要进一步优化（例如用二维单调栈直接统计矩形）。

---