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 T5「砂の城 2 / Sandcastle 2」

由 ChatGPT 4.1 翻译