@[Oier_szc](/user/368204) AC code:
```cpp
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
vector<ll> X1,X2,Y1,Y2;
ll calc(vector<ll> &a){
sort(a.begin(),a.end());
vector<ll> b;
b.clear();
for(int i=1;i<a.size();++i)
b.push_back(a[i]-a[i-1]);
ll res=0;
for(int i=0;i<b.size();++i){
res+=b[i]*(i+1)*(b.size()-i);
}
return res;
}
int main(){
int n,x,y;
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d%d",&x,&y);
if((x+y)%2==0){
X1.push_back((x+y)/2);
Y1.push_back((y-x)/2);
}
else{
X2.push_back((x+y)/2);
Y2.push_back((y-x+1)/2);
}
}
ll ans=0;
ans+=calc(X1);
ans+=calc(X2);
ans+=calc(Y1);
ans+=calc(Y2);
printf("%lld\n",ans);
return 0;
}
```
by Greenzhe @ 2024-04-27 21:47:11
@[Oier_szc](/user/368204) [jiangly的极简代码](https://atcoder.jp/contests/abc351/submissions/52875772)
by yyrwlj @ 2024-04-27 21:49:25
@[Oier_szc](/user/368204) 首先你把坐标归为两类（类似棋盘黑格白格）。所以在每类之间可以相互跳。对于这两类，分别把坐标重新编号（旋转 45°），然后问题转换为求任意两点之间曼哈顿距离和。
by Greenzhe @ 2024-04-27 21:50:15
然后考虑对 x 坐标和 y 坐标分别处理。
对于每个坐标先排个序、求差分。
然后就转换为差分序列里所有非空段的和。
考虑每个元素被哪些区间统计到。
然后做完了。
by Greenzhe @ 2024-04-27 21:52:49
@[Oier_szc](/user/368204) 绷我一开始想维护：
$$\sum_{1 \le i < j \le n} \max(|x_i-x_j|,|y_i-y_j|)$$
的时候打算无脑 $2$ 种情况扔进主席树里暴力，然后发现不对可以有简单做法。
by Composite_Function @ 2024-04-27 22:00:44
@[Composite_Function](/user/531746) +1，但是毒瘤主席树过的人确实不可能这么多（）
by Oier_szc @ 2024-04-27 22:04:16
@[Oier_szc](/user/368204) 切比雪夫距离转曼哈顿。
~~我还以为这已经这么众所周知了吗？~~
~~所以是有其它做法吗？~~
by fresh_boy @ 2024-04-28 00:45:01
@[Oier_szc](/user/368204) 你需要知道这个：
$\max\{x,y\} = \dfrac{x + y + |x - y|}{2}$。
by sgl654321 @ 2024-04-28 08:47:23
@[sgl654321](/user/525374) 卧槽/bx
by Oier_szc @ 2024-04-28 18:09:49
题已经A了，此帖结。
by Oier_szc @ 2024-04-28 18:10:26