P5781 [IOI 2019] 矩形区域

19 世纪初，统治者下令在俯瞰美丽河景的高原上建造一座宫殿。这块高原被看做是一个由正方形单元格组成的 $n \times m$ 网格。网格的行从 $0$ 到 $n-1$ 编号，列从 $0$ 到 $m-1$ 编号。第 $i$ 行第 $j$ 列（$0 \le i \le n-1$，$0 \le j \le m-1$）的单元格记为单元格 $(i,j)$。每个单元格 $(i,j)$ 有特定的海拔高度，记为 $a_{i,j}$。 统治者指示他的建筑师选择一个矩形区域来建造宫殿。该区域不能包含网格边界（第 $0$ 行，第 $n-1$ 行，第 $0$ 列，以及第 $m-1$ 列）上的任何单元格。为此，建筑师应选出四个整数 $r_1$，$r_2$，$c_1$ 和 $c_2$（$1 \le r_1 \le r_2 \le n-2$ 且 $1 \le c_1 \le c_2 \le m-2$)，对应于包括所有满足 $r_1 \le i \le r_2$ 且 $c_1 \le j \le c_2$ 的单元格 $(i,j)$ 的矩形区域。 此外，一个区域被认为是合法的，当且仅当对于该区域中的每个单元格 $(i,j)$，以下条件成立：对于与该区域相邻的、位于第 $i$ 行的两个单元格（单元格 $(i,c_1-1)$ 和 $(i,c_2+1)$），以及与该区域相邻的、位于第 $j$ 列的两个单元格（单元格 $(r_1-1,j)$ 和 $(r_2+1,j)$），单元格 $(i,j)$ 的海拔高度必须严格小于这四个单元格的海拔高度。 你的任务是帮助建筑师统计可建宫殿的合法区域的数量（也就是所对应区域为合法的 $r_1$，$r_2$，$c_1$ 和 $c_2$ 的数量）。

第一行，两个整数 $n$ 和 $m$，表示网格的长和宽。 接下来 $n$ 行，第 $i$ 行 $m$ 个整数，为 $a_{i-1,0\dots m-1}$。

一行，一个整数，表示合法区域的数量。

**样例解释**  一共有 $6$ 个合法区域，分别为： - $r_1=r_2=1, c_1=c_2=1$ - $r_1=1, r_2=2, c_1=c_2=1$ - $r_1=r_2=1, c_1=c_2=3$ - $r_1=r_2=4, c_1=2,c_2=3$ - $r_1=r_2=4, c_1=c_2=3$ - $r_1=3,r_2=4,c_1=c_2=3$ 例如，$r_1=1, r_2=2, c_1=c_2=1$ 对应一个合法区域，原因是以下两个条件都成立： - $a_{1,1}=4$ 严格小于 $a_{0,1}=8$，$a_{3,1}=14$，$a_{1,0}=7$，和 $a_{1,2}=10$。 - $a_{2,1}=7$ 严格小于 $a_{0,1}=8$，$a_{3,1}=14$，$a_{2,0}=9$，和 $a_{2,2}=20$。 **数据范围** 对于所有数据： - $1 \le n, m \le 2500$。 - $0 \le a_{i,j} \le 7 \times 10^6 (0 \le i \le n - 1, 0 \le j \le m - 1)$。 详细子任务附加限制与分值如下表： |子任务编号|附加限制|分值| |:-:|:-:|:-:| |$1$|$n, m \le 30$|$8$| |$2$|$n, m \le 80$|$7$| |$3$|$n, m \le 200$|$12$| |$4$|$n, m \le 700$|$22$| |$5$|$n \le 3$|$10$| |$6$|$0 \le a_{i,j} \le 1$|$13$| |$7$|没有任何附加限制|$28$|