【模板】KD-tree

KD-tree：

将空间内的点进行合理划分，以支持有关高维点的操作。

其实就是将线段树搬到了二维及更高维度上。

注意$KD-tree$虽然很像线段树，但其实是一棵二叉搜索树，空间复杂度是$O(n)$的。

查询时本质是一个搜索+剪枝，时间复杂度最优$O(logn)$，期望$O(\sqrt{n})$。

没了。

代码（[CQOI2016]K远点对）：

#include<bits/stdc++.h>
#define maxn 100005
#define maxm 500005
#define inf 1ll<<62
#define ll long long
#define debug(x) cerr<<#x<<": "<<x<<endl
#define fgx cerr<<"--------------"<<endl
#define dgx cerr<<"=============="<<endl

using namespace std;
struct node{int x[2];}p[maxn];
int n,K,np,tot,ls[maxn],rs[maxn];
int id[maxn],mx[maxn][2],mn[maxn][2];
priority_queue<ll,vector<ll>,greater<ll> > q;

inline int read(){
    int x=0,f=1; char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*f;
}

inline ll dis(ll xa,ll ya,ll xb,ll yb){return (xa-xb)*(xa-xb)+(ya-yb)*(ya-yb);}
inline bool cmp(node a,node b){
    if(!np) return (a.x[0]==b.x[0])?(a.x[1]<b.x[1]):(a.x[0]<b.x[0]);
    else return (a.x[1]==b.x[1])?(a.x[0]==b.x[0]):(a.x[1]<b.x[1]);
}

inline ll getdis(node po,int k){
    ll res=0;
    for(int i=0;i<2;i++){
        ll a=abs(po.x[i]-mx[k][i]),b=abs(po.x[i]-mn[k][i]);
        res+=max(a*a,b*b);
    }
    return res;
}
inline void pushup(int k){
    for(int i=0;i<2;i++){
        mn[k][i]=mx[k][i]=p[id[k]].x[i];
        if(ls[k]) mn[k][i]=min(mn[k][i],mn[ls[k]][i]),mx[k][i]=max(mx[k][i],mx[ls[k]][i]);
        if(rs[k]) mn[k][i]=min(mn[k][i],mn[rs[k]][i]),mx[k][i]=max(mx[k][i],mx[rs[k]][i]);
    }
}
inline int build(int l,int r,int op){
    if(l>r) return 0;
    int mid=l+r>>1,k=++tot; np=op,id[k]=mid;
    nth_element(p+l,p+mid,p+1+r,cmp);
    ls[k]=build(l,mid-1,op^1);
    rs[k]=build(mid+1,r,op^1);
    pushup(k); return k;
}
inline void query(node po,int k){
    ll d=dis(po.x[0],po.x[1],p[id[k]].x[0],p[id[k]].x[1]);
    if(d>q.top()) q.pop(),q.push(d);
    ll dl=-inf,dr=-inf;
    if(ls[k]) dl=getdis(po,ls[k]);
    if(rs[k]) dr=getdis(po,rs[k]);
    if(dl>dr){
        if(dl>q.top()) query(po,ls[k]);
        if(dr>q.top()) query(po,rs[k]);
    }
    else{
        if(dr>q.top()) query(po,rs[k]);
        if(dl>q.top()) query(po,ls[k]);
    }
    return;
}

int main(){
    n=read(),K=read();
    for(int i=1;i<=n;i++) p[i].x[0]=read(),p[i].x[1]=read();
    build(1,n,0);
    for(int i=1;i<=2*K;i++) q.push(0);
    for(int i=1;i<=n;i++) query(p[i],1);
    printf("%lld\n",q.top());
    return 0;
}

[CQOI2016]K远点对