Lvat_s Blog

模版题

每个点只向每个象限里最近的点连边

离散化后树状数组维护就好了

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
 
const long long N=50005,LIMIT=1000000000,INF=210000000000000ll;
 
long long n,f[N],Fir[10*N],Sec[10*N],cnt,Line[10*N],Num[10*N],tot,ans;
 
struct Point{
long long x,y,id;
friend bool operator<(Point A,Point B){return (A.x<B.x)|(A.x==B.x && A.y<B.y);}
}poi[N];
 
struct Edge{
long long x,y,len;
Edge(){}
Edge(long long sa,long long sb,long long sc){x=sa;y=sb;len=sc;}
friend bool operator<(Edge A,Edge B){return A.len<B.len;}
}e[20*N];
 
long long Find(long long x){return f[x]==x?x:f[x]=Find(f[x]);}
void Union(long long x,long long y){if(x>y)f[x]=y;else f[y]=x;}
long long lowbit(long long x){return x&(-x);}
void AddBIT(long long x,long long y,long long z){while(x){if(Fir[x]>y){Fir[x]=y;Sec[x]=z;}x-=lowbit(x);}}
long long QueBIT(long long x){long long Mx=LIMIT*2,Ex=0;while(x<=n){if(Mx>Fir[x]){Mx=Fir[x];Ex=Sec[x];}x+=lowbit(x);}return Ex;}
long long Abs(long long x){return x>0?x:-x;}
long long Dist(Point A,Point B){return Abs(A.y-B.y)+Abs(A.x-B.x);}
 
int main(){
freopen("2177.in","r",stdin);
freopen("2177.out","w",stdout);
scanf("%lld",&n);
for(long long i=1;i<=n;i++){scanf("%lld %lld",&poi[i].x,&poi[i].y);poi[i].id=i;}
for(long long i=1;i<=4;i++){
    if(i==3)for(long long i=1;i<=n;i++)poi[i].x=LIMIT-poi[i].x;
    if(i==2 || i==4)for(long long i=1;i<=n;i++)swap(poi[i].x,poi[i].y);
    sort(poi+1,poi+n+1);
    for(long long i=1;i<=n;i++)Line[i]=poi[i].y-poi[i].x;
    sort(Line+1,Line+n+1);
    for(long long i=1;i<=n;i++)Num[i]=lower_bound(Line+1,Line+n+1,poi[i].y-poi[i].x)-Line;
    for(long long i=1;i<=n;i++)Fir[i]=INF;
    for(long long i=n;i>=1;i--){
        long long Set=QueBIT(Num[i]);
        if(Set)e[++cnt]=Edge(poi[i].id,poi[Set].id,Dist(poi[i],poi[Set]));
        AddBIT(Num[i],poi[i].y+poi[i].x,i);
    }
}
sort(e+1,e+cnt+1);
for(long long i=1;i<=n;i++)f[i]=i;
for(long long i=1;i<=cnt && tot<n-1;i++){
    if(Find(e[i].x)!=Find(e[i].y)){
        tot++;
        Union(Find(e[i].x),Find(e[i].y));
        ans+=1ll*e[i].len;
    }
}
printf("%lld\n",ans);
return 0;
}