KDtree

KDT

为多维的点构造相对平衡的二叉树结构（空间划分）

原理：每次按照某维排序（可以按顺序依次，也可随机，貌似按方差大的维更优），取中间点作为当前点，递归左右区间

时间复杂度(O(n^{1-frac1w}),w)为维度

题意：求平面上第K远点对的距离

(N100000K100)

//K-D tree 
#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return f==1?x:-x;
}
#define ll long long
const int N=1e5+4;
const ll inf=1e18;
struct pnt{int x[2];}g[N];
inline ll sqr(int x){return (ll)x*x;}//long long!!!
inline int get(int l,int r){//找方差最大的最优 
	double ax=0,ay=0,bx=0,by=0,mod=r-l+1;
	for(int i=l;i<=r;i++){
		ax+=g[i].x[0];bx+=g[i].x[1];
		ay+=sqr(g[i].x[0]);by+=sqr(g[i].x[1]);
	}
	ax=ay*mod-ax*ax;bx=by*mod-bx*bx;
	if(ax>bx)return 0;
	return 1; 
}
int opt,n,k;
inline bool cmp(const pnt &y,const pnt &z){
	return y.x[opt]<z.x[opt];
} 
priority_queue<ll>q;
#define lc L[p]
#define rc R[p]
#define max_(a,b) (a>b?a:b)
#define min_(a,b) (a>b?b:a)
struct K_D_tree{
	int mx[N<<1][2],mn[N<<1][2],L[N<<1],R[N<<1],cnt=0;
	pnt d[N<<1];
	inline void pushup(int p){
		for(int i=0;i<2;i++)mx[p][i]=mn[p][i]=d[p].x[i];
		if(lc)for(int i=0;i<2;i++){
			mx[p][i]=max_(mx[p][i],mx[lc][i]);
			mn[p][i]=min_(mn[p][i],mn[lc][i]);
		}
		if(rc)for(int i=0;i<2;i++){
			mx[p][i]=max_(mx[p][i],mx[rc][i]);
			mn[p][i]=min_(mn[p][i],mn[rc][i]);
		}
	}
	inline void build(int &p,int l,int r){
		if(l>r)return;
		p=++cnt;
		int mid=l+r>>1;
		opt=get(l,r);//切换维度
		nth_element(g+l,g+mid,g+r+1,cmp);//把mid小的放在mid位置处，大的放后面，小的放前面 
		d[p]=g[mid];
		build(lc,l,mid-1);build(rc,mid+1,r);
		pushup(p); 
	}
	inline ll calc(pnt a,pnt b){
		return sqr(a.x[0]-b.x[0])+sqr(a.x[1]-b.x[1]);
	}
	inline ll deal(pnt a,int b){//所在子树可能最远的点 
		return max_(sqr(a.x[0]-mx[b][0]),sqr(a.x[0]-mn[b][0]))+max_(sqr(a.x[1]-mx[b][1]),sqr(a.x[1]-mn[b][1]));
	}
	inline void query(int p,pnt y){//最坏sqrt(n) 最优logn^2 
		ll dl=-inf,dr=-inf;
		if(lc)dl=deal(y,lc);
		if(rc)dr=deal(y,rc);
		ll di=calc(y,d[p]);
		if(-q.top()<di){q.pop();q.push(-di);}//找到了更大的点
		if(dl>dr){
			if(-q.top()<dl)query(lc,y);
			if(-q.top()<dr)query(rc,y);
		} 
		else{
			if(-q.top()<dr)query(rc,y);
			if(-q.top()<dl)query(lc,y); 
		}
	}
}T; 
int main(){
	srand(time(0));
	n=read();k=read();
	for(int i=1;i<=n;i++){g[i].x[0]=read();g[i].x[1]=read();} 
	for(int i=1;i<=(k<<1);i++)q.push(0);
	T.build(T.L[0],1,n);
	for(int i=1;i<=n;i++)T.query(1,g[i]);
	printf("%lld
",-q.top());
	return (0-0);
}