题目翻译

一个 $n\times m$ 的网格，每个格子里有 $1$ 个数，问对于所有相同的数，曼哈顿距离总和是多少？

曼哈顿距离：$a_{i_1,j_1}$ 与 $a_{i_2,j_2}$ 距离为 $\left|i_1-i_2\right|+\left|j_1-j_2\right|$。

题目思路

暴力搜一遍，肯定挂掉，$n\times m$ 有 $100000$。

所以，我们对每种数进行分类，每一类再分成 $x$ 轴的总距离求和加上 $y$ 轴的总距离求和。

这是蒟蒻我能想到的最优解了。

分析思路

那么总距离求和该怎么做呢，例如上文的 $x$ 轴的总距离求和。

我们考虑把它们排序，放在一根数轴上。

我们以端点为 $i_2$ 和 $i_3$ 的线段做例子：

本身长度 $2$。

往右边走，有 $i_3,i_4,i_5$，产生 $3$ 次贡献。

左边每个点都可以与上面 $3$ 个点产生连接，左边有 $2$ 个点，$i_1$ 和 $i_2$。

注意，线段的两个端点也算进去。

那么这个线段产生左边端点个数 $\times$ 线段长度 $\times$ 右边端点个数这么多贡献。

同理，每个线段也产生上述贡献。

AC 代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct node
{
    int x,y;//记录x轴和y轴
};
vector<node>a[100020];//对数字分类
ll s(vector<int>a)//求和
{
    ll sum=0;
    for(int i=1;i<a.size();i++)
    {
        sum+=i*(a[i]-a[i-1])*(a.size()-i);
    }
    return sum;
}
void solve()
{
    int n,m,maxx=INT_MIN;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int z;
            cin>>z;
            node zz;
            zz.x=i;
            zz.y=j;
            a[z].push_back(zz);//插入这个点信息
            maxx=max(z,maxx);//找出最大值
        }
    }
    ll sum=0;
    for(int i=1;i<=maxx;i++)
    {
        vector<int>xx;//记录x轴
        vector<int>yy;//记录y轴
        for(auto j:a[i])//插入点的信息
        {
            xx.push_back(j.x);
            yy.push_back(j.y);
        }
        //排序
        sort(xx.begin(),xx.end());
        sort(yy.begin(),yy.end());
        ll sx=s(xx);
        ll sy=s(yy);
        sum+=sx+sy;//求和
    }
    cout<<sum<<endl;
}
int main()
{
    int t=1;
    while(t--)
    {
        solve();
    }
    return 0;
}