P13543 [OOI 2022] Strange sum

Egor 有一个 $n \times m$ 的表格，行编号为 $1$ 到 $n$，列编号为 $1$ 到 $m$。每个格子被涂成了一种颜色，颜色用 $1$ 到 $10^9$ 的整数表示。 我们用 $(r, c)$ 表示第 $r$ 行第 $c$ 列的格子。定义两个格子 $(r_1, c_1)$ 和 $(r_2, c_2)$ 之间的 $\textit{曼哈顿距离}$ 为它们之间最短路径的长度，其中每一步只能走到相邻的格子（即有公共边的格子）。路径可以经过任意颜色的格子。例如，$(1, 2)$ 到 $(3, 3)$ 的曼哈顿距离为 $3$，一种最短路径为 $(1, 2) \to (2, 2) \to (2, 3) \to (3, 3)$。 Egor 想计算所有颜色相同的格子之间两两曼哈顿距离的总和。请你帮他计算这个和。

第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq m$，$n \cdot m \leq 500\,000$），分别表示表格的行数和列数。 接下来的 $n$ 行，每行 $m$ 个整数 $c_{i1}, c_{i2}, \ldots, c_{im}$（$1 \le c_{ij} \le 10^9$），表示第 $i$ 行每个格子的颜色。

输出一个整数，表示所有颜色相同的格子之间两两曼哈顿距离的总和。

### 说明 在第一个样例中，相同颜色的格子有三对：$(1, 1)$ 和 $(2, 3)$，$(1, 2)$ 和 $(2, 2)$，$(1, 3)$ 和 $(2, 1)$。它们的曼哈顿距离分别为 $3$、$1$ 和 $3$，总和为 $7$。 ### 评分说明 本题测试数据分为 5 组。只有通过某一组的全部测试点，且通过部分之前组的全部测试点，才能获得该组分数。注意，有些分组不要求通过样例测试点。 记 $C$ 为表格中颜色的最大数量。 | 组别 | 分值 | $n$ | $n \cdot m$ | $C$ | 必须通过的组 | 备注 | |:----:|:----:|:---:|:-----------:|:---:|:------------:|:----:| | 0 | 0 | -- | -- | -- | -- | | 样例测试点 | | 1 | 23 | -- | $n \cdot m \le 1000$ | -- | 0 | | | 2 | 17 | $n = 1$ | -- | -- | -- | | | | 3 | 15 | $n = 2$ | -- | -- | -- | | | | 4 | 20 | -- | -- |$C \le 2$ | | | | 5 | 25 | -- | -- | -- | -- | 0--4 | |