[ABC351E] Jump Distance Sum 讲解

zrl123456 · 2024-04-28 15:30:30 · 题解

题目

考察：思维。
题目简述：
定义 \text{dist}(A,B) 表示：

• 一开始它在 A 点。
• 设 A 点坐标为 (x,y)，然后它可以向 (x+1,y+1),(x+1,y-1),(x-1,y-1),(x-1,y+1) 移动一步，\text{dist}(A,B) 为移动的最小步数。
• 当其永远无法达到时，\text{dist}(A,B)=0。

给你 n 个点，其坐标分别为 A_i，求 \displaystyle\sum_{i=1}^{n-1}\sum_{j=i+1}^n\text{dist}(A_i,A_j)。

我们很容易分析出 \text{dist}((x_i,y_i),(x_j,y_j))=\max(x_i-x_j,y_i-y_j)，在 (x_i+y_i)\bmod 2\ne(x_j+y_j)\bmod 2 时，\text{dist}((x_i,y_i)(x_j,y_j))=0。
暴力模拟的话，时间复杂度为 O(n^2)，无法通过 n\le 2\times 10^5 的数据。

我们可以尝试把他转化成曼哈顿距离，如图：
我们将其旋转 45 度，使 (0,0) 还是 (0,0)，这样 (0,2) 变成了 (-1,1)。
我们很容易发现 (x,y) 变成了 \displaystyle(\frac{x_i+y_i}{2},\frac{y_i-x_i}{2})。
以上是 (x_i+y_i)\bmod 2=0 的情况，(x_i+y_i)\bmod 2=1 时我们只需要让 y_i 减去 1 就可以了。

这样，式子就变成了 \displaystyle\sum_{i=1}^{n-1}\sum_{j=i+1}^n|x_i-x_j|+|y_i-y_j|，那么我们可以排一个序（值是不变的），然后：

然后我们可以维护前缀和（\displaystyle sumx_x=\sum_{i=1}^xx_i,sumy_x=\sum_{i=1}^xy_i），这样：

这样就可以了。

代码：

#include<bits/stdc++.h>
#define int long long
#define inl inline
#define INF LLONG_MAX
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define rer(i,x,y,cmp) for(int i=x;i<=y&&cmp;++i)
#define per(i,x,y) for(int i=x;i>=y;--i)
#define FAST ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl '\n'
using namespace std;
const int N=4e5+5;
int n,x[N],y[N],ans;
vector<int>gx[5],gy[5];
signed main(){
    FAST;
    cin>>n;
    rep(i,1,n) cin>>x[i]>>y[i];
    rep(i,1,n){
        int k=(x[i]^y[i])&1;
        gx[k].push_back((x[i]+y[i]-k)>>1);
        gy[k].push_back((y[i]-x[i]-k)>>1);
    }
    rep(i,0,1){
        sort(gx[i].begin(),gx[i].end());
        sort(gy[i].begin(),gy[i].end());
    }
    rep(k,0,1){
        int sumx=0,sumy=0,siz=gx[k].size();
        rep(i,0,siz-1){
            int x=gx[k][i],y=gy[k][i];
            ans+=x*i-sumx+y*i-sumy;
            sumx+=x;
            sumy+=y;
        }
    }
    cout<<ans;
    return 0;
}