题目描述

难度分:$1400$

输入$n$，$m(1 \leq n \times m \leq 10^5)$和$n$行$m$列的矩阵$a$，元素范围$[1,10^5]$。

对于矩阵中的所有相同元素对，即满足$a[x_1][y_1] = a[x_2][y_2]$的元素对$(a[x_1][y_1], a[x_2][y_2])$，把$|x_1-x_2|+|y_1-y_2|$加到答案中。

注意$(a,b)$和$(b,a)$只算一次，输出答案。

输入样例$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

算法

前缀和

用哈希表$mp$构建一个映射“元素值 $\rightarrow$ 索引列表”，然后遍历每个元素值对答案的贡献。对于一个元素值$val$，它的索引列表为$pos$，以$pos$长度为$4$为例，此时$val$对答案的贡献为

$|x_4-x_3|+|x_4-x_2|+|x_4-x_1|+|x_3-x_2|+|x_2-x_1|+|y_4-y_3|+|y_4-y_2|+|y_4-y_1|+|y_3-y_2|+|y_2-y_1|$

此时我们发现$x$和$y$是独立的，分开来看，并且如果$x$坐标和$y$坐标如果有序并不影响答案，就能直接把绝对值拿掉，上式就会被化简为

$\Sigma_{i=2}^{4}((i-1) \times x_i-\Sigma_{j=1}^{i-1}x_j + (i-1) \times y_i-\Sigma_{j=1}^{i-1}y_j)$

这样我们先将$x$坐标和$y$坐标分成两个数组$xs$和$ys$分别排序，然后遍历一遍$xs$和$ys$，在这个过程中维护子数组$[1,i)$的前缀和就能计算出元素$val$对答案的贡献。依次计算每个元素的贡献，累加起来就能得到答案。

复杂度分析

时间复杂度

构建映射$mp$的时间复杂度为$O(nm)$，对每个$val$处理存在排序操作，排序是性能瓶颈，一共对$nm$个位置进行了排序，时间复杂度为$O(nmlog_2{nm})$，这也是算法整体的时间复杂度。

空间复杂度

算法需要存储每个元素的位置二元组，而一共有$nm$个元素，因此算法整体的额外空间复杂度在$O(nm)$级别。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <array>
#include <vector>
#include <unordered_map>

using namespace std;
typedef long long LL;

int n, m, a;

LL get(vector<array<int, 2>>& tup) {
    int sz = tup.size();
    vector<LL> xs, ys;
    for(int i = 0; i < sz; i++) {
        xs.push_back(tup[i][0]);
        ys.push_back(tup[i][1]);
    }
    sort(xs.begin(), xs.end());
    sort(ys.begin(), ys.end());
    LL res = 0, presumX = xs[0], presumY = ys[0];
    for(int i = 1; i < sz; i++) {
        LL dx = xs[i] - xs[i - 1], dy = ys[i] - ys[i - 1];
        res += xs[i]*i - presumX;
        res += ys[i]*i - presumY;
        presumX += xs[i];
        presumY += ys[i];
    }
    return res;
}

int main() {
    scanf("%d%d", &n, &m);
    unordered_map<int, vector<array<int, 2>>> mp;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            scanf("%d", &a);
            mp[a].push_back({i, j});
        }
    }
    LL ans = 0;
    for(auto&[val, pos]: mp) {
        ans += get(pos);
    }
    printf("%lld\n", ans);
    return 0;
}