struct Node{int d[2],mi[2],ma[2],ch[2];}p[N<<1],now;
int n,m,D,cnt,root,ans;
inline int cmp(Node a,Node b){return a.d[D]<b.d[D];}
inline void push_up(int o){
p[o].mi[0]=min(p[o].d[0],min(p[lc].mi[0],p[rc].mi[0]));
p[o].mi[1]=min(p[o].d[1],min(p[lc].mi[1],p[rc].mi[1]));
p[o].ma[0]=max(p[o].d[0],max(p[lc].ma[0],p[rc].ma[0]));
p[o].ma[1]=max(p[o].d[1],max(p[lc].ma[1],p[rc].ma[1]));
}
inline int dis(Node a,Node b){return fabs(a.d[0]-b.d[0])+fabs(a.d[1]-b.d[1]);}
void Build(int &o,int l,int r,int d){
D=d,o=(l+r)>>1;nth_element(p+l,p+o,p+r+1,cmp);
// for(int i=1;i<=n;i++) printf("%d %d\n",p[i].d[0],p[i].d[1]);
if(l<o) Build(lc,l,o-1,d^1);if(r>o) Build(rc,o+1,r,d^1);
push_up(o);
}
void insert(int &o,int d){
if(!o) o=++cnt,p[o]=now;
else if(now.d[d]<p[o].d[d]) insert(lc,d^1);
else insert(rc,d^1);
push_up(o);
}
int Calc(int o){
return max(p[o].mi[0]-now.d[0],0)+max(now.d[0]-p[o].ma[0],0)+
max(p[o].mi[1]-now.d[1],0)+max(now.d[1]-p[o].ma[1],0);
}
void Query(int o){
if(!o) return;
ans=min(ans,dis(p[o],now));
int ll=INF,rr=INF;
if(lc) ll=Calc(lc);if(rc) rr=Calc(rc);
if(ll<rr){
if(ll<ans) Query(lc);
if(rr<ans) Query(rc);
}
else{
if(rr<ans) Query(rc);
if(ll<ans) Query(lc);
}
}
转自BeiYu-oi's Blog
