题目描述

题目译自 Open Olympiad in Informatics 2022 Day1 T3 「Странная сумма / Strange sum」。

叶戈尔有一个 $n \times m$ 的表格，行从上到下编号为 $1$ 到 $n$，列从左到右编号为 $1$ 到 $m$。表格中的每个单元格被涂上某种颜色，颜色用从 $1$ 到 $10^{9}$ 的整数编号表示。

我们将位于第 $r$ 行和第 $c$ 列的单元格表示为 $(r, c)$。定义单元格 $(r_1, c_1)$ 和 $(r_2, c_2)$ 之间的曼哈顿距离为两单元格之间最短路径的长度，其中路径上的任意相邻单元格必须共享一条边。例如，在一个 $3 \times 4$ 的表格中，单元格 $(1, 2)$ 和 $(3, 3)$ 之间的曼哈顿距离为 $3$，一条最短路径为 $(1, 2) \to (2, 2) \to (2, 3) \to (3, 3)$。注意，路径可以经过任意颜色的单元格。

叶戈尔想计算所有相同颜色单元格对之间的曼哈顿距离之和。请帮助叶戈尔计算这个总和。

输入格式

输入文件的第一行包含两个整数 $n$ 和 $m$ $(1 \leq n \leq m, n \cdot m \leq 500000)$，分别表示表格的行数和列数。

接下来的 $n$ 行描述表格的每一行。第 $i$ 行包含 $m$ 个整数 $c_{i1}, c_{i2}, \ldots, c_{im}$ $(1 \leq c_{ij} \leq 10^{9})$，表示表格第 $i$ 行中各单元格的颜色。

输出格式

输出一个整数，即所求的曼哈顿距离之和。

2 3
1 2 3
3 2 1

7

在第一个样例中，有三对相同颜色的单元格：位于坐标 $(1, 1)$ 和 $(2, 3)$ 的单元格，位于坐标 $(1, 2)$ 和 $(2, 2)$ 的单元格，以及位于坐标 $(1, 3)$ 和 $(2, 1)$ 的单元格。它们对应的曼哈顿距离分别为 $3$、$1$ 和 $3$，总和为 $7$。

3 4
1 1 2 2
2 1 1 2
2 2 1 1

76

4 4
1 1 2 3
2 1 1 2
3 1 2 1
1 1 2 1

129

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。