AT_joi2022ho_e 砂の城 2 (Sandcastle 2)

JOI 君正在沙滩上玩耍。他建造了一座沙堡。这座由 JOI 君建造的沙堡位于沙滩上的一个矩形区域内。这个矩形区域有 $H$ 行 $W$ 列。位于从上往下的第 $i$ 行、从左往右的第 $j$ 列的格子的高度为 $A_{i, j}$。**注意所有 $A_{i, j}$ 的值互不相同。** 在沙堡上，JOI 君执行了如下操作： 1. 首先，JOI 君选择一个格子，从该格子开始移动。 2. 然后，他可以从当前格子出发，向上下左右四个方向之一移动到相邻的格子。他必须移动到高度低于当前格子的格子。他可以重复此操作零次或多次。 最终，如果我们从上往下俯视，他经过的格子将形成一个矩形。 给定每个格子的高度信息 $A_{i, j}$，请编写程序计算所有可能的由 JOI 君经过的格子组成的矩形的数量。

第一行包含两个正整数 $H, W$。 接下来 $H$ 行，每行 $W$ 个正整数，表示 $A_{i, 1}, A_{i, 2}, \ldots, A_{i, W}$。

输出一行，一个整数，表示所有可能的由 JOI 君经过的格子组成的矩形的数量。

**【样例解释 \#1】** 由于有 $10$ 个可能的由 JOI 君经过的格子组成的矩形，输出 $10$。  这个样例满足所有子任务的限制。 **【样例解释 \#2】** 由于有 $15$ 个可能的由 JOI 君经过的格子组成的矩形，输出 $15$。  这个样例满足子任务 $2, 3, 4, 5$ 的限制。 **【样例解释 \#3】** 举个例子，如下矩形可以由 JOI 君经过的格子组成。由于总共有 $65$ 个可能的矩形，输出 $65$。  这个样例满足子任务 $2, 3, 4, 5$ 的限制。 ---- **【数据范围】** **本题采用捆绑测试。** 对于 $100\%$ 的数据，$1 \le H, W, H \cdot W \le 5 \times 10^4$，$1 \le A_{i, j} \le 10^7$，$A_{i_1, j_1} \ne A_{i_2, j_2}$（$(i_1, j_1) \ne (i_2, j_2)$）。 - 子任务 $1$（$9$ 分）：$H = 1$。 - 子任务 $2$（$10$ 分）：$H \cdot W \le 100$。 - 子任务 $3$（$5$ 分）：$H \cdot W \le 1500$。 - 子任务 $4$（$56$ 分）：$H \cdot W \le 7000$。 - 子任务 $5$（$20$ 分）：无特殊限制。 ---- **译自 [JOI 2022 Final](https://www.ioi-jp.org/joi/2021/2022-ho/index.html) T5「[砂の城 2 ](https://www.ioi-jp.org/joi/2021/2022-ho/2022-ho-t5.pdf) / [Sandcastle 2](https://www.ioi-jp.org/joi/2021/2022-ho/2022-ho-t5-en.pdf)」** 由 ChatGPT 4.1 翻译