本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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|$，那么我们可以排一个序（值是不变的），然后： $$\sum_{i=1}^{n-1}\sum_{j=i+1}^nx_j+y_j-x_i-y_i=\sum_{j=2}^n\sum_{i=1}^{j-1}x_j+y_j-x_i-y_i$$ 然后我们可以维护前缀和（$\displaystyle sumx_x=\sum_{i=1}^xx_i,sumy_x=\sum_{i=1}^xy_i$），这样：
$$\sum_{j=2}^n\sum_{i=1}^{j-1}x_j+y_j-x_i-y_i=\sum_{j=2}^n(j-1)(x_j+y_j)-sumx_{j-1}-sumy_{j-1}$$ 这样就可以了。

代码：

#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;
}