[51nod1213]二维曼哈顿距离最小生成树

　　二维平面上有N个坐标为整数的点，点x1 y1同点x2 y2之间的距离为：横纵坐标的差的绝对值之和，即：Abs(x1 - x2) + Abs(y1 - y2)（也称曼哈顿距离）。求这N个点所组成的完全图的最小生成树的边权之和。
　Input
　　第1行：1个数N，表示点的数量。(2 <= N <= 50000)
　　第2 - N + 1行：每行2个数，表示点的坐标(0 <= x, y <= 1000000)
　Output
　　输出N个点所组成的完全图的最小生成树的边权之和。

就当是攒新板子了。。

题解：http://blog.****.net/acm_cxlove/article/details/8890003

 #include<cstdio>
 #include<iostream>
 #include<cstring>
 #include<algorithm>
 #include<queue>
 #include<cmath>
 #include<cstdlib>
 #define ll long long
 #define ull unsigned long long
 #define ui unsigned int
 //#define d double
 #define ld long double
 const int maxn=,inf=;
 struct zs{int x,y,v,id;}a[maxn],aa[maxn],e[maxn<<];int ne;
 struct zs1{int v,id;}t[maxn],b[maxn];
 int fa[maxn];
 int i,j,k,n,m;
 ll ans;

 int ra,fh;char rx;
 inline int read(){
     rx=getchar(),ra=,fh=;
     while(rx<''&&rx!='-')rx=getchar();
     if(rx=='-')fh=-,rx=getchar();
     while(rx>='')ra=ra*+rx-,rx=getchar();return ra*fh;
 }

 inline int abs(int x){return x<?-x:x;}
 inline int getdis(int a,int b){
     return abs(aa[a].x-aa[b].x)+abs(aa[a].y-aa[b].y);
 }
 inline void insert(int a,int b){
     /*e[++tot].too=b,e[tot].pre=last[a],last[a]=tot,
     e[++tot].too=a,e[tot].pre=last[b],last[b]=tot,
     e[tot-1].dis=e[tot].dis=getdis(a,b);*/
     e[++ne]=(zs){a,b,getdis(a,b)};
 }

 bool operator <(zs a,zs b){return a.x<b.x||(a.x==b.x&&a.y<b.y);}
 bool operator <(zs1 a,zs1 b){return a.v<b.v;}
 bool cmpe(zs a,zs b){return a.v<b.v;}

 inline void mins(zs1 &a,zs1 b){if(b.v<a.v)a=b;}
 inline void add(int x,zs1 mn){while(x<=n)mins(t[x],mn),x+=x&-x;}
 inline int query(int x){zs1 mn=(zs1){inf,-};while(x)mins(mn,t[x]),x-=x&-x;return mn.id;}
 inline void run(){
     int i,cnt=;
     for(i=;i<=n;i++)t[i]=(zs1){inf,-};
     for(i=;i<=n;i++)b[i]=(zs1){a[i].y-a[i].x,i};
     std::sort(b+,b++n);
     for(i=;i<=n;a[b[i].id].v=n-cnt+,i++)cnt+=b[i].v!=b[i-].v||i==;
     std::sort(a+,a++n);
     for(i=n;i;i--){
         int id=query(a[i].v);
         if(id>)insert(a[i].id,id);
         add(a[i].v,(zs1){a[i].x+a[i].y,a[i].id});
     }
 }

 inline int getfa(int x){return fa[x]!=x?fa[x]=getfa(fa[x]):x;}
 int main(){
     n=read();
     for(i=;i<=n;i++)aa[i].x=read(),aa[i].y=read();

     for(i=;i<=n;i++)a[i].x=aa[i].x,a[i].y=aa[i].y,a[i].id=i;
     run();

     for(i=;i<=n;i++)a[i].x=aa[i].x,a[i].y=-aa[i].y,a[i].id=i;
     run();

     for(i=;i<=n;i++)a[i].x=aa[i].y,a[i].y=aa[i].x,a[i].id=i;
     run();

     for(i=;i<=n;i++)a[i].x=-aa[i].y,a[i].y=aa[i].x,a[i].id=i;
     run();

     std::sort(e+,e++ne,cmpe);
     for(i=;i<=n;i++)fa[i]=i;
     for(i=;i<=ne;i++)if(getfa(e[i].x)!=getfa(e[i].y))
         fa[fa[e[i].x]]=fa[e[i].y],ans+=e[i].v;
     printf("%lld\n",ans);
 }