#1516. 一键挖矿

一键挖矿

题目描述

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

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

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

每个方块有一个在 11nmnm 之间的权值,记作 w<i,j>w_{\left<i,j\right>},所有方块的权值互不相同。你可以选定两个参数 l,rl,r,满足 1lrnm1\le l\le r\le nm。在此参数作用下,所有权值在 [l,r][l,r] 外的方块将会虚化,只留下所有权值在 [l,r][l,r] 内的方块。形式化地说,一个方块 <i,j>\left<i,j\right> 会被保留当且仅当 lw<i,j>rl\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,rl,r 的方法,使得在参数作用下,能够使用一键挖矿 Mod 在不触发 bug 的情况下一次性采集所有未虚化的机关方块。

输入格式

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

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

输出格式

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

样例 1

2 3
1 2 3
4 5 6
13

选择 <l,r>\left<l,r\right>1313 种方案如下:

形成 1×11\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×21\times 2 的矩形区域:$\left<1,2\right>,\left<2,3\right>,\left<4,5\right>,\left<5,6\right>$。</p>

形成 1×31\times 3 的矩形区域:<1,3>,<4,6>\left<1,3\right>,\left<4,6\right>

形成 2×32\times 3 的矩形区域:<1,6>\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.inveinminer3.ans

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

数据范围与提示

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

对于所有测试点:1w<i,j>nm2×1051\le w_{\left<i,j\right>}\le nm\le2\times10^5

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

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

子任务编号 nn\le mm\le w<i,j>=m(i1)+jw_{\left<i,j\right>}=m(i-1)+j
121\sim2 11 20002000 不保证
363\sim6 2×1052\times10^5
7107\sim10 22
111211\sim12 100100
131413\sim14 2×1052\times10^5 保证
152015\sim20 不保证

Author: PinkRabbit