← 返回题目列表

Codeforces · 1648/A

A. 奇怪的总和

中文机器翻译题面 查看原题

Egor 有一个大小为 $$$n \times m$$$ 的表,行编号从 $$$1$$$ 到 $$$n$$$,列编号从 $$$1$$$ 到 $$$m$$$。每个单元格都有一个颜色,可以表示为从 $$$1$$$ 到 $$$10^5$$$ 的整数。

让我们将位于第 $$$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)$$$。

Egor 决定计算每对相同颜色的单元格之间的曼哈顿距离之和。帮他算一下这个总数。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n \le m$$$, $$$n \cdot m \leq 100\,000$$$) — 表中的行数和列数。

接下来的 $$$n$$$ 行描述表中的一行。第 $$$i$$$ 行包含 $$$m$$$ 整数 $$$c_{i1}, c_{i2}, \ldots, c_{im}$$$ ($$$1 \le c_{ij} \le 100\,000$$$) - 第 $$$i$$$ 行中单元格的颜色。

输出

打印一个整数 - 每对相同颜色的单元格之间的曼哈顿距离之和。

示例

输入 #1

2 3
1 2 3
3 2 1

输出 #1

7

输入 #2

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

输出 #2

76

输入 #3

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

输出 #3

129

注意

在第一个示例中,有三对相同颜色的单元格:在单元格 $$$(1, 1)$$$ 和 $$$(2, 3)$$$ 中,在单元格 $$$(1, 2)$$$ 和 $$$(2, 2)$$$ 中,在单元格 $$$(1, 3)$$$ 和 $$$(2, 1)$$$ 中。它们之间的曼哈顿距离为 $$$3$$$、$$$1$$$ 和 $$$3$$$,总和为 $$$7$$$。