kd-tree模板

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