ABC351E 补题笔记

批：赛时很快想到切比雪夫后就跳进主席树里出不来了。

一个很妙的题。

首先分 \(x+y\) 的奇偶性黑白染色后黑色和白色不可达。

然后对于同一个颜色的点易得 \(dis=\max(|x1-x2|,|y1-y2|)\) ，即切比雪夫距离。

这个时候就可以直接上主席树了，但太复杂不是正解。

最简单的解法是：我们充分发扬人类智慧，将点绕原点转 \(45\) 度再变长 \(\sqrt{2}\) 倍，也就是令坐标变成 \((x+y,x-y)\) 。

可以发现四种操作变成了 \((x+y+2,x-y)\) , \((x+y-2,x-y)\) , \((x+y,x-y+2)\) , \((x+y,x-y-2)\) ，于是直接变成了求曼哈顿距离除以 \(2\) 。由此也可以得到一个将切比雪夫距离变成曼哈顿距离的重要 trick 。

对于求曼哈顿距离之和的具体实现还可以像jly代码一样分两次拆贡献，也是一个非常高妙的写法。 \bx

code

#include <bits/stdc++.h>
//#include <windows.h>
#define ED cerr<<endl;
#define TS cerr<<"I AK IOI"<<endl;
#define cr(x) cerr<<x<<endl;
#define cr2(x,y) cerr<<x<<" "<<y<<endl;
#define cr3(x,y,z) cerr<<x<<" "<<y<<" "<<z<<endl;
#define cr4(x,y,z,w) cerr<<x<<" "<<y<<" "<<z<<" "<<w<<endl;
#define pii pair<int,int>
#define fi first
#define se second
#define int long long
using namespace std;
const int N=1e3+5,INF=2e9,mod=1e9+7;
int n,m,ans=0;
vector<int> xs[2],ys[2];
int get(vector<int> s)
{
	sort(s.begin(),s.end());
	int res=0,sz=s.size();
	for(int i=1;i<sz;++i) res+=(s[i]-s[i-1])*i*(sz-i);
	return res;
}
signed main()
{
	scanf("%lld",&n);
	int x,y;
	for(int i=1;i<=n;++i)
	{
		scanf("%lld%lld",&x,&y);
		int t=(x+y)&1ll;
		xs[t].emplace_back(x+y);
		ys[t].emplace_back(x-y);
	}
	int ans=get(xs[0])+get(xs[1])+get(ys[0])+get(ys[1]);
	ans/=2ll;
	printf("%lld",ans);
	return 0;
}