题目描述
Source: Codeforces Round #539 (Div. 1) F & IOI 2018 Day1 T2
2098 年 4 月,Terraria 发布了 1.7 版本更新。
更新日志中显示,这个版本添加了一种新的机关,占用 n×m 的矩形区域。将这个区域中第 i 行第 j 列的方块记作 ⟨i,j⟩。
每个方块有一个在 1 到 nm 之间的权值,记作 w⟨i,j⟩,所有方块的权值互不相同。你可以选定两个参数 l,r,满足 1≤l≤r≤nm。在此参数作用下,所有权值在 [l,r] 外的方块将会虚化,只留下所有权值在 [l,r] 内的方块。形式化地说,一个方块 ⟨i,j⟩ 会被保留当且仅当 l≤w⟨i,j⟩≤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⟨i,1⟩∼w⟨i,m⟩ 表示第 i 行的方块的权值。保证所有方块的权值互不相同。
输出格式
输出仅一行一个整数表示选择参数的方案数。
样例 1
2 3
1 2 3
4 5 6
13
选择 ⟨l,r⟩ 的 13 种方案如下:
形成 1×1 的矩形区域:⟨1,1⟩,⟨2,2⟩,⟨3,3⟩,⟨4,4⟩,⟨5,5⟩,⟨6,6⟩。
形成 1×2 的矩形区域:⟨1,2⟩,⟨2,3⟩,⟨4,5⟩,⟨5,6⟩。
形成 1×3 的矩形区域:⟨1,3⟩,⟨4,6⟩。
形成 2×3 的矩形区域:⟨1,6⟩。
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∼12 一致。
数据范围与提示
注意:本题评测采用子任务方式,必须通过子任务下的所有测试点才能获得该子任务的分数。保证一个子任务下的测试点个数不超过 3 个。
对于所有测试点:1≤w⟨i,j⟩≤nm≤2×105。
保证所有 w⟨i,j⟩ 互不相同。
每个子任务下的测试点的具体限制见下表:
子任务编号 |
n≤ |
m≤ |
w⟨i,j⟩=m(i−1)+j |
1∼2 |
1 |
2000 |
不保证 |
3∼6 |
2×105 |
7∼10 |
2 |
11∼12 |
100 |
13∼14 |
2×105 |
保证 |
15∼20 |
不保证 |
Author: PinkRabbit