涉及知识点：博弈、贪心
题意
Alice 和 Bob 在玩选点游戏，所有的点在一个 \(k\) 维空间中，他们轮流选走一个点放入自己的集合中，Alice 先手。定义集合 \(S\) 的权值 \(val(S)\) 为集合中点两两之间的 \(k\) 维曼哈顿距离之和。Alice 的得分为 \(val(S_A)-val(S_B)\)，Bob 的得分为 \(val(S_B)-val(S_A)\)，两人都想最大化自己的得分且采用最优策略，请问 Alice 最终得分为多少。
有 \(2n\) 个点，\(1\leq n\times k\leq 10^5\)。
思路
将得分表示出来进行转换，则 Alice 的得分显然为：
\[\sum_{i,j\in S_A,i<j}dis(i,j)-\sum_{i,j\in S_B,i<j} \]此时两边同时加上 \(\sum_{i,j\in S_B,i>j}dis(i,j)+\sum_{i\in S_A,j\in S_B}dis(i,j)\)：
\[\begin{equation*} \begin{aligned} &[\sum_{i,j\in S_A,i<j}dis(i,j)+\sum_{i,j\in S_B,i>j}dis(i,j)+\sum_{i\in S_A,j\in S_B}dis(i,j)]-[\sum_{i,j\in S_B,i<j}dis(i,j)+\sum_{i,j\in S_B,i>j}dis(i,j)+\sum_{i\in S_A,j\in S_B}dis(i,j)] \\ =& [\sum_{i,j\in S_A,i<j}dis(i,j)+\sum_{i,j\in S_B,i<j}dis(i,j)+\sum_{i\in S_A,j\in S_B}dis(i,j)]-[\sum_{i,j\in S_B}dis(i,j)+\sum_{i\in S_A,j\in S_B}dis(i,j)] \\ =& \sum_{i,j\in S_A\cup S_B,i<j}dis(i,j)-\sum_{i\in S_A\cup S_B,j\in S_B}dis(i,j) \end{aligned} \end{equation*} \]因此，Alice 的得分为空间中所有点两两之间的距离之和减去所有点到 \(S_B\) 的距离之和，前者是一个固定值，因此 Alice 想要得分更高，就必须要使得 \(S_B\) 中的点到所有点距离和最小，她得抢在 Bob 前把距离和大的点放到 \(S_A\) 中；然而由于 Bob 的得分是 Alice 的相反数，所以他想使得 \(S_B\) 中的点到所有点距离和最大，他想尽可能取距离和大的点放在 \(S_B\) 中。因此我们将每个点到所有点的距离和算出来并大到小排序，Alice 和 Bob 轮流取最大的点。
将边权化为点权，每个点的点权设为自己到其他所有点的距离之和，这样一来假设两个点 \(a,b\) 分别属于 \(S_A,S_B\) 那么它们点权相减时，它们之间的距离正好可以抵消；假设两个点属于同一个集合，那么它们之间的距离就会被算两次。因此 Alice 的得分即为 \(\frac{\sum S_A-\sum S_B}{2}\)。
那么，如何计算一个点到所有点的距离和呢？肯定不能直接 \(O(n^2k)\) 计算。这里涉及一个小 Trick，由于曼哈顿距离的计算维度之间是不相干扰的，因此可以将每维拆开来计算，将所有点在该维度上的位置从小到大排序，再用前后缀和来计算，这么做是 \(O(kn\log n)\) 的，具体可以参考代码 52-61 行。
代码
用的是此处的答案统计方式。
#include<bits/stdc++.h>
using namespace std;
#ifdef ONLINE_JUDGE
#define getchar __getchar
inline char __getchar(){
static char ch[1<<20],*l,*r;
return (l==r&&(r=(l=ch)+fread(ch,1,1<<20,stdin),l==r))?EOF:*l++;
}
#endif
template<class T>inline void rd(T &x){
T res=0,f=1;
char ch=getchar();
while(ch<'0' || ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while('0'<=ch && ch<='9'){res=res*10+ch-'0';ch=getchar();}
x=res*f;
}
template<class T>inline void wt(T x,char endch='\0'){
static char wtbuff[20];
static int wtptr;
if(x==0){
putchar('0');
}
else{
if(x<0){x=-x;putchar('-');}
wtptr=0;
while(x){wtbuff[wtptr++]=x%10+'0';x/=10;}
while(wtptr--) putchar(wtbuff[wtptr]);
}
if(endch!='\0') putchar(endch);
}
typedef pair<int,int> pii;
typedef long long LL;
const int MAXN=2e5+5;
int n,k;
vector<int>v[MAXN];
vector<pii>dim;
LL dissum[MAXN],ans=0;
int main(){
freopen("ys.in","r",stdin);
freopen("ys.out","w",stdout);
rd(n);rd(k);
for(int i=1;i<=2*n;i++){
v[i].resize(k);
for(int j=0;j<k;j++){
rd(v[i][j]);
}
}
for(int i=0;i<k;i++){
dim.clear();
for(int j=1;j<=2*n;j++) dim.emplace_back(v[j][i],j);
sort(dim.begin(),dim.end());
LL presum=0;
for(int j=0;j<dim.size();j++){
dissum[dim[j].second]+=1LL*dim[j].first*j-presum;
presum+=dim[j].first;
}
presum=0;
for(int j=dim.size()-1;j>=0;j--){
dissum[dim[j].second]+=presum-1LL*dim[j].first*(dim.size()-1-j);
presum+=dim[j].first;
}
}
sort(dissum+1,dissum+1+2*n,greater<LL>());
for(int i=1;i<=2*n;i+=2)
ans+=dissum[i]-dissum[i+1];
wt(ans/2);
return 0;
}