[AdditionalFile3666.zip](file://AdditionalFile3666.zip?type=additional_file)

#3666. 「JOI 2022 Final」沙堡 2

标签: 传统 | 时间限制: 4000 ms | 内存限制: 1024 MiB |

题目描述

译自 JOI 2022 Final T5「砂の城 2 / Sandcastle 2」

JOI 君在沙滩上堆沙堡，他已经做好了一个沙堡，沙堡可以使用一个 $H\times W$ 的二维矩形表示，其被划分成若干个 $1\times 1$ 的小格子，格子高度互相不同。

JOI 君决定在沙堡上游走，他可以从任意一个点出发，向上下左右四个方向行走，必须满足他行走的路径单调下降。

出于一些原因，JOI 君想知道，在他所有可能的行走路径中，恰好覆盖了一个子矩形的路径数有多少条。

输入格式

第一行两个整数 $H,W$。

接下来 $H$ 行，一行 $W$ 个数字 $A_{i,j}$ 表示 $(i,j)$ 这个格子的高度。

输出格式

一行一个整数，表示恰好覆盖了一个子矩形的路径数有多少条。

样例 1

输入

1 5
2 4 7 1 5

输出

10

这个样例满足所有子任务的限制。

样例 2

输入

3 2
18 10
19 12
17 13

输出

15

这个样例满足子任务 $2,3,4,5$ 的限制。

样例 3

输入

3 5
83 47 36 38 40
13 10 26 68 67
15 19 20 70 90

输出

65

方案太多了，仅列举几种：

这个样例满足子任务 $2,3,4,5$ 的限制。

数据范围

对于全部数据，$H,W\ge 1$，$HW\le 5\times 10^4$，$1\le A_{i,j}\le 10^7$，$A_{i,j}$ 互不相同。