题意分析

计算所有颜色相同的格子之间两两曼哈顿距离的总和。

解法分析

最朴素的想法：暴力枚举

我们使用一个 map 记录同种颜色格子的坐标，随后对于每一种颜色的格子，枚举格子 $i$ 和 $j$。每一次在变量 $ans$ 之中累加 $| x_i - x_j | + | y_i - y_j |$。显然，该方法时间复杂度过高，最坏可以达到 $O(n^2m^2)$。

进阶算法：前缀和

对于同种颜色的格子，我们注意到：可以分别计算两个坐标对于答案的贡献。
对于所有格子的 $x$ 坐标，可以使用先排序，再利用前缀和的方法，计算点对差的绝对值之和。
假设我们有一列排序好的数 $x_1,x_2 \dots x_n$，对于第 $i$ 个数 $x_i$，对于答案的贡献即为：

对于 $\sum _ {k=1} ^ {i-1} x_k$，可以使用前缀和进行维护。
此方法对 $y$ 轴坐标同理。

代码实现

前缀和数组和 $ans$ 变量需要开 long long。

#include <bits/stdc++.h>

using namespace std;
map < int, vector < pair < int, int >>> rc;
int n, m;
long long ans = 0;
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int col;
            cin >> col;
            // 投入map中
            if (rc.find(col) != rc.end()) {
                rc[col].push_back(make_pair(i, j));
            } else {
                vector < pair < int, int >> tmp;
                tmp.push_back(make_pair(i, j));
                rc[col] = tmp;
            }
        }
    }
    for (auto p = rc.begin(); p != rc.end(); p++) {
        vector < pair < int, int >> points = p -> second;
        vector < int > x_pos;
        vector < int > y_pos;
        vector < long long > sum_x;
        vector < long long > sum_y;
        for (int i = 0; i < points.size(); i++) {
            x_pos.push_back(points[i].first);
            y_pos.push_back(points[i].second);
        }
        // 排序
        sort(x_pos.begin(), x_pos.end());
        sort(y_pos.begin(), y_pos.end());
        // 前缀和计算
        for (int i = 0; i < points.size(); i++) {
            if (i == 0) {
                sum_x.push_back(x_pos[i]);
                sum_y.push_back(y_pos[i]);
            } else {
                sum_x.push_back(sum_x[i - 1] + x_pos[i]);
                sum_y.push_back(sum_y[i - 1] + y_pos[i]);
            }
        }
        for (int i = 1; i < points.size(); i++) {
            // 统计答案
            ans += (long long)(i) * x_pos[i] - sum_x[i - 1];
            ans += (long long)(i) * y_pos[i] - sum_y[i - 1];
        }
    }
    cout << ans << endl;
}