题目描述

Source: Codeforces Round #539 (Div. 1) F & IOI 2018 Day1 T2

2098 年 4 月，Terraria 发布了 1.7 版本更新。

更新日志中显示，这个版本添加了一种新的机关，占用 $n\times m$ 的矩形区域。将这个区域中第 $i$ 行第 $j$ 列的方块记作 $\left<i,j\right>$。

每个方块有一个在 $1$ 到 $nm$ 之间的权值，记作 $w_{\left<i,j\right>}$，所有方块的权值互不相同。你可以选定两个参数 $l,r$，满足 $1\le l\le r\le nm$。在此参数作用下，所有权值在 $[l,r]$ 外的方块将会虚化，只留下所有权值在 $[l,r]$ 内的方块。形式化地说，一个方块 $\left<i,j\right>$ 会被保留当且仅当 $l\le w_{\left<i,j\right>}\le r$。

你发现 1.7 版本仍兼容七十年前已停止更新的 tModLoader v1.23.7。你高兴地载入修改日期为 2020/9/21 19:44 的 VeinMiner.tmod 一键挖矿 Mod，想要试试它能不能对新的机关起作用。

一键挖矿 Mod 可以一次性采集所有与初始挖掘方块四连通的未虚化的方块。也就是说，可以利用这个 Mod 采集所有的与初始挖掘方块在同一四连通块内的方块。

但是因为 Terraria 1.7 对方块更新进行了优化，所以这个 Mod 有一个 bug：如果所有与初始挖掘方块四连通的方块没有形成一个矩形区域，则无法完整地把这些方块全部采集下来。

你想知道有多少种选择参数 $l,r$ 的方法，使得在参数作用下，能够使用一键挖矿 Mod 在不触发 bug 的情况下一次性采集所有未虚化的机关方块。

输入格式

第一行两个正整数 $n, m$，意义见题目描述。

接下来 $n$ 行，第 $i$ 行一共 $m$ 个正整数 $w_{\left<i,1\right>}\sim w_{\left<i,m\right>}$ 表示第 $i$ 行的方块的权值。保证所有方块的权值互不相同。

输出格式

输出仅一行一个整数表示选择参数的方案数。

样例 1

2 3
1 2 3
4 5 6

13

选择 $\left<l,r\right>$ 的 $13$ 种方案如下：

形成 $1\times 1$ 的矩形区域：$\left<1,1\right>,\left<2,2\right>,\left<3,3\right>,\left<4,4\right>,\left<5,5\right>,\left<6,6\right>$。</p>

形成 $1\times 2$ 的矩形区域：$\left<1,2\right>,\left<2,3\right>,\left<4,5\right>,\left<5,6\right>$。</p>

形成 $1\times 3$ 的矩形区域：$\left<1,3\right>,\left<4,6\right>$。

形成 $2\times 3$ 的矩形区域：$\left<1,6\right>$。

4 4
4 1 5 6
3 13 7 11
2 14 8 9
16 15 12 10

32

样例 3

见选手目录下的 veinminer3.in 与 veinminer3.ans。

该样例的数据类型与最终测试点 $11 \sim 12$ 一致。

数据范围与提示

注意：本题评测采用子任务方式，必须通过子任务下的所有测试点才能获得该子任务的分数。保证一个子任务下的测试点个数不超过 3 个。

对于所有测试点：$1\le w_{\left<i,j\right>}\le nm\le2\times10^5$。

保证所有 $w_{\left<i,j\right>}$ 互不相同。

每个子任务下的测试点的具体限制见下表：

子任务编号	$n\le$	$m\le$	$w_{\left<i,j\right>}=m(i-1)+j$
$1\sim2$	$1$	$2000$	不保证
$3\sim6$		$2\times10^5$
$7\sim10$	$2$
$11\sim12$	$100$
$13\sim14$	$2\times10^5$		保证
$15\sim20$			不保证

---

Author: PinkRabbit