自动搬运

查看原文

来自洛谷，原作者为

	FFTotoro 龙猫

搬运于2025-08-24 21:33:43，当前版本为作者最后更新于2025-04-18 15:05:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

本文在结论的证明上参考了：曼哈顿距离最小生成树 - 博客园，在此表示对作者的感谢。

下文中对于平面中的两个点 $A$ 和 $B$，记 $|AB|$ 表示 $A$ 和 $B$ 的曼哈顿距离，即 $|AB|=|x_A-x_B|+|y_A-y_B|$。

对于完全图最小生成树一类题，一种直接的想法是使用蓝莓算法解决。但是我们将会在这里介绍一种直接使用 Kruskal 的解法。

观察到本题边数很多，而 Kruskal 是基于边的贪心，所以只有一条道路——去掉必然不会被选择的边，只保留少量的边求解。

先给出结论：对于每个点 $(x,y)$，如下图将平面划分为 $8$ 个 $45\degree$ 的区域（$(x,y)$ 为四条分割线的交点，其中两条分割线分别与 $x$ 轴与 $y$ 轴平行），将该点与每个区域中离它最近的任意一个点连边即可。下证为什么这样的连边方式是最优的。

证明：

设 $(x,y)$ 为原点 $O(0,0)$，在上面的 $R_1$ 中考虑两个点 $A(x_1,y_1),B(x_2,y_2)$（其他区域同理；由于在区域 $R_1$ 中所以满足 $0\le x_1\le y_1$ 和 $0\le x_2\le y_2$），不妨认为 $|OA|\le |OB|$。根据最小生成树的性质，对于原图的一个三元环，其中的最长边一定不会被选入最小生成树，故只需证：$|AB|\le |OB|$，即 $OB$ 可以被忽略。

分类讨论 $x_1,x_2,y_1,y_2$ 四者的关系：

• $x_1>x_2\land y_1>y_2$：与 $|OA|\le |OB|$ 矛盾；
• $x_1\le x_2\land y_1>y_2$：此时 $|AB|=x_2-x_1+y_1-y_2$，故 $|OB|-|AB|=x_2+y_2-(x_2-x_1+y_1-y_2)=x_1-y_1+2y_2$。如果 $|OB|<|AB|$ 则有 $y_1>x_1+2y_2$，故有 $|OA|=x_1+y_1>2x_1+2y_2$，$|OB|=x_2+y_2\le 2y_2<|OA|$，与 $|OA|\le |OB|$ 矛盾；
• $x_1>x_2\land y_1\le y_2$：与 $x_1\le x_2\land y_1>y_2$ 的情况同理；
• $x_1\le x_2\land y_1\le y_2$：此时 $|OA|+|AB|=|OB|$，始终满足 $|AB|\le |OB|$。

综上，该结论成立。

现在的问题在于，如何找出这些边。可以观察到一个事情，事实上只需要考虑区域 $R_1,R_2,R_3,R_4$ 中的点进行连边（因为每条边必然有一个点 $x$ 坐标较小，相当于将其与 $x$ 坐标较大的连边），常数能够除以 $2$。

考虑如何快速找到单个区域中离一个点 $A(x,y)$ 最近的点：以区域 $R_1$ 为例，对于一个点 $B(x',y')$，由于在区域 $R_1$ 所以满足 $x'\ge x\land y'-x'\ge y-x$，又因为 $|AB|=x'-x+y'-y$，所以需要最小化 $x'+y'$。

对于这一类二维偏序问题，考虑按其中一维排序，在数据结构上维护另一维。观察到需要维护的是最值，又由于需要求值的下标范围是一个后缀，所以直接上树状数组维护。

求解除了 $R_1$ 以外的其他区域很简单，只需要合理地组合使用下面的操作进行坐标变换即可：

• 交换 $x$ 坐标和 $y$ 坐标，即将一个点关于直线 $x=y$ 轴对称；
• 将 $x$ 坐标取相反数，即将一个点关于直线 $x=0$ 轴对称。

时间复杂度 $O(n\log n)$。

参考代码（GNU C++ 17）：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tpi;
namespace IAOI_lib{
  template<typename T> class dsu{
    private:
      vector<T> a;
      vector<int> s;
    public:
      dsu(){
        a.resize(200000),s.resize(200000,1);
        iota(a.begin(),a.end(),0);
      }
      dsu(int n){
        a.resize(n),s.resize(n,1);
        iota(a.begin(),a.end(),0);
      }
      T leader(T x){
        return a[x]==x?x:a[x]=leader(a[x]);
      }
      inline int size(T x){
        return s[leader(x)];
      }
      inline void merge(T x,T y){
        x=leader(x),y=leader(y);
        if(x==y)return;
        if(s[x]>s[y])swap(x,y);
        s[y]+=s[x],a[x]=y;
      }
      inline bool same(T x,T y){
        return leader(x)==leader(y);
      }
  }; // 并查集模板
  template<typename T,T(*op)(T,T),T(*e)()> class fenwick_tree{
    private:
      vector<T> t;
    public:
      fenwick_tree(){
        t.resize(200000,e());
      }
      fenwick_tree(int n){
        t.resize(n,e());
      }
      inline int lowbit(int x){
        return x&-x;
      }
      inline void add(int p,T d){
        t[p]=op(t[p],d),p++;
        while((p-=lowbit(p))>0)
          t[p-1]=op(t[p-1],d);
      }
      inline T suf_sum(int p){
        T s=t[p++];
        while((p+=lowbit(p))<=t.size())
          s=op(s,t[p-1]);
        return s;
      }
  }; // 维护后缀信息的树状数组模板
  inline pii mn(pii x,pii y){return x<y?x:y;}
  inline pii id(){return make_pair(2e9,-1);}
  inline pair<ll,vector<pii> > mst(vector<tpi> e,int n=1){
    vector<pii> e2;
    for(auto [u,v,w]:e)n=max({n,u+1,v+1});
    sort(e.begin(),e.end(),[](tpi x,tpi y){
      return get<2>(x)<get<2>(y);
    });
    dsu<int> d(n); ll r=0;
    for(auto [u,v,w]:e)
      if(!d.same(u,v))d.merge(u,v),e2.emplace_back(u,v),r+=w;
    return make_pair(r,e2);
  } // Kruskal 求解最小生成树
  inline pair<ll,vector<pii> > manhattan_mst(vector<pii> p){
    vector<tpi> e;
    for(int r1=0;r1<2;r1++){
      for(auto &[x,y]:p)x=-x;
      for(int r2=0;r2<2;r2++){
        vector<int> a(p.size()),b;
        for(auto &[x,y]:p)
          swap(x,y),b.emplace_back(x);
        sort(b.begin(),b.end());
        b.erase(unique(b.begin(),b.end()),b.end());
        auto get=[&](int x){
          return lower_bound(b.begin(),b.end(),x)-b.begin();
        }; // 对坐标离散化
        iota(a.begin(),a.end(),0);
        sort(a.begin(),a.end(),[&](int x,int y){
          int dx=p[x].second-p[x].first,dy=p[y].second-p[y].first;
          return dx==dy?p[x].first>p[y].first:dx>dy;
        }); // 对第一维排序
        fenwick_tree<pii,mn,id> t(b.size());
        for(int i=0;i<p.size();i++){
          auto [x,y]=p[a[i]];
          int w=get(x);
          auto [s,j]=t.suf_sum(w);
          if(~j)e.emplace_back(a[i],a[j],s-x-y);
          t.add(w,make_pair(x+y,i));
        } // 树状数组求距离最短点
      }
    }
    return mst(e);
  }
}
int main(){
  ios::sync_with_stdio(false);
  int n; cin>>n;
  vector<pii> a(n);
  for(auto &[x,y]:a)cin>>x>>y;
  auto [w,e]=IAOI_lib::manhattan_mst(a);
  cout<<w<<endl;
  for(auto [u,v]:e)cout<<u+1<<' '<<v+1<<'\n';
  return 0;
}