题解：P13543 [OOI 2022] Strange sum

· · 题解

题目传送门

题目分析

把颜色相同的点分为一类，显然我们可以求出每一类中的点两两之间的曼哈顿距离，再把每一类的答案相加。

对于每一类内部，n 个点,第 i 个点坐标为 (x_i,y_i)，两两之间的曼哈顿距离等于

\sum_{\mathclap{1\le i< j\le n}}(\left| x_j-x_i\right|+\left| y_j-y_i\right|)

拆开得

\sum_{\mathclap{1\le i< j\le n}}\left| x_j-x_i\right|+\sum_{\mathclap{1\le i<j\le n}}\left| y_j-y_i\right|

因此每类之内可以分别对横坐标和纵坐标求解。两者的方法是一样的，下面给出对横坐标求解的方法。

由于对横坐标求解，因此不用考虑纵坐标，我们可以把所有点压缩到一个横向的数轴上。乱序显然很难求解，因此先对所有点按横坐标从大到小排序。排序的好处是，上面式子中的绝对值可以不要了。数轴上，我们将第 i 个点与第 i-1 个点形成的线段称作线段 i。显然，线段 i 的长度 S_i 为 x_i-x_{i-1}。因此第 i 个点与第 j 个点（i<j）间的距离为

\sum\limits_{k=i+1}^j S_k

设一类中两两之间横坐标的差，即对横坐标求解的答案为 A_x，则

\begin{aligned} A_x &= \sum_{\mathclap{1\le i< j\le n}}\left| x_j-x_i\right| \\ &=\sum_{1\le i< j\le n}\sum\limits_{k=i+1}^j S_k \\&=\sum\limits_{k=1}^{n-1} P_k\times S_k \end{aligned}

其中 P_k 表示满足 i<k，j\ge k 的二元组 (i,j) 的数量。这是因为如果计算从 i 点到 j 点横坐标之差，必然会计算一次 S_k。的这是最关键的一步，没有理解的话可以手动画一下数轴和线段。

下面考虑求出 P_k。如果 n-1 为偶数，即线段数为偶数。此时可以 n-1 条线段分为对称的前 \frac{n-1}{2} 条与后 \frac{n-1}{2} 条。先对前 \frac{n-1}{2} 条求解 P。上面的二元组可以看成一条从 i 点开始，结束于 j 点的线段，记为线段 IJ，显然 P_k 等于覆盖了线段 k 的线段 IJ 的数量。我们如果固定线段 IJ 的长度，问题就变成一条定长的线段从左到右移动，覆盖了线段 k 多少次。

如图，上文所说的线段 k 在图中为线段 f，点数 n=15。如果线段 IJ 的长度很短，满足 \left| IJ \right|< k，如图中的线段 h。此时线段 IJ 覆盖线段 k（图中为 f）的次数为 \left| IJ \right|，如图中的线段 h，i，j 就是长度为 3 的线段 IJ 三次覆盖 f。若 IJ 的长度再大一些，满足 k\le \left| IJ \right|\le n-k，此时从点 k 到点 j（见上文）的部分虽然在 IJ 中，但无论如何不会覆盖线段 k，此时线段 IJ 覆盖线段 k（图中为 f）的次数为 k。如上图中线段 k 到 q 都覆盖了 f，共 6 次。若 IJ 的长度特别大，满足 \left| IJ \right|>n-k。如图中的线段 a（位置稍有偏差，左端点应位于 2 处），即使 f 还在 IJ 内，但 IJ 已经移到头了，不能再移了。此时覆盖次数为 n-\left| IJ \right|。因此最终

\begin{aligned} P_k &= \sum\limits_{i=1}^{k-1}i+k\times (n-2k+1)+\sum\limits_{i=n-k+1}^{n-1}i \\ &= k\times (k-1)+k\times (n-2k+1)\\ &= k\times (n-k)\end{aligned}

别忘了，这只是前 \frac{n-1}{2} 条线段的 P。由于后 \frac{n-1}{2} 条线段与前 \frac{n-1}{2} 条线段完全对称，可以看作 IJ 从右往左移动，因此答案一样，都是 k\times (n-k)。还有 n-1 为奇数的情况。该情况与 n-1 为偶数的情况唯一的区别是位于正中间的第 \frac{n}{2} 条线段。而

\begin{aligned} P_{\frac{n}{2}}&=2\times \sum\limits_{i=1}^{k-1}i+k\\ &= k\times (k-1)+k\\ &= k\times k\\ &=k\times \frac{n}{2}\\ &= k\times (n-k) \end{aligned}

因此得出结论，P_k=k\times (n-k)，则横坐标的答案为 \sum\limits_{k=1}^{n-1} k\times(n-k)\times S_k。纵坐标按相同的方法计算即可。

代码

#include<bits/stdc++.h>
#define N 500001 
using namespace std;
struct point{
    long long x,y;
};
vector<point>p[N];
int h=1,h2=0;
map<int,int> jl;
long long jl2[N];
int cmp1(point a,point b){
    return a.x<b.x;
}
int cmp2(point a,point b){
    return a.y<b.y;
}
int main(){
    int n,m;
    cin>>n>>m;
    for(long long i=1;i<=n;i++){
        for(long long j=1;j<=m;j++){
            long long k;
            cin>>k;
            if(!jl[k]){
                jl[k]=h;
                h++;
                jl2[++h2]=k;
            }
            p[jl[k]].push_back((point){i,j});
        }
    }
    long long ans=0;
    for(int i=1;i<=h2;i++){
        long long kn=jl2[i];
        sort(p[jl[kn]].begin(),p[jl[kn]].end(),cmp1);
        long long n0=p[jl[kn]].size()-1;
        for(long long j=1;j<p[jl[kn]].size();j++){
            ans+=j*(n0+1-j)*(p[jl[kn]][j].x-p[jl[kn]][j-1].x);
        }
        sort(p[jl[kn]].begin(),p[jl[kn]].end(),cmp2);
        for(long long j=1;j<p[jl[kn]].size();j++){
            ans+=j*(n0+1-j)*(p[jl[kn]][j].y-p[jl[kn]][j-1].y);
        }
    }
    cout<<ans;
    return 0;
}