#CW77. 差值求和(sum)

差值求和(sum)

题目描述

给定一个大小为 n×mn \times m 的表格,行编号为 1,2,…,n1, 2, \ldots, n,列编号为 1,2,…,m1, 2, \ldots, m。第 ii 行第 jj 列的格子记为 (i,j)(i, j),并带有颜色 ci,jc_{i,j}。

两个格子之间只能沿公共边移动。格子 (r1,c1)(r_1, c_1) 与 (r2,c2)(r_2, c_2) 的曼哈顿距离定义为从一个格子走到另一个格子所需的最少步数,即 ∣r1−r2∣+∣c1−c2∣|r_1 - r_2| + |c_1 - c_2|。

请计算所有颜色相同且位置不同的格子对的曼哈顿距离之和,每一对只计算一次。

输入格式

从 sum.in 文件中读入。

第一行包含两个整数 n,mn, m,满足 1≤n≤m1 \le n \le m 且 n⋅m≤500000n \cdot m \le 500000。接下来 nn 行,每行包含 mm 个整数 ci,1,ci,2,…,ci,mc_{i,1}, c_{i,2}, \ldots, c_{i,m},满足 1≤ci,j≤1091 \le c_{i,j} \le 10^9。

输出格式

向 sum.out 文件中输出。

输出一个整数,表示所求的距离总和。答案可能超过 32 位有符号整数范围。

样例 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

数据范围

所有输入数据均为整数。设 CC 为表格中出现的不同颜色数。

本题采用子任务捆绑计分:通过一个子任务的全部测试点,才能获得该子任务的分数。

子任务 分值 测试点 附加条件
1 23 1∼51 \sim 5 n⋅m≤1000n \cdot m \le 1000
2 17 6∼96 \sim 9 n=1n = 1
3 15 10∼1210 \sim 12 n=2n = 2
4 20 13∼1613 \sim 16 C≤2C \le 2
5 25 17∼2017 \sim 20 无额外限制