[BZOJ] [P3053] [가장 가 까 운 M 포인트] [문제 풀이] [kdtree]

전송 문:http://www.lydsy.com/JudgeOnline/problem.php?id=3053
@ nilihan 1999 신 번 이 kdtree 를 업데이트 하지 않 았 으 니 스스로 배 울 수 밖 에...
쓰 고 나 니 역시 니 리 한 이 없어 요. 1999 빨리 = =,
또 다른 키 트 리 에 들 어 갈 지 여 부 를 어떻게 판단 해 야 할 지 잘 모 르 겠 어 요.
닐 리 한 1999 신 번 을 봤 다 면

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cctype>
#include<queue>
#include<cstring>
using namespace std;
const int maxn=50005;
int n,m,root,D;
typedef long long LL;
struct point{
	int d[5],mx[5],mn[5],l,r,ind;
	point():l(0),r(0),ind(0){};
	int& operator[](int x){return d[x];}
	bool operator<(point p)const{return d[D]<p[D];}
}p[maxn];
priority_queue<pair<LL,int> >Q;
int getint(){
	int res=0,f=1;char c=getchar();
	while(!isdigit(c))f=f==-1||c=='-'?-1:1,c=getchar();
	while(isdigit(c))res=res*10+c-'0',c=getchar();
	return res*f;
}
LL sqr(LL x){return x*x;}
LL dis(point a,point b){
	LL ans=0;
	for(int i=0;i<m;i++)ans+=sqr(a[i]-b[i]);
	return ans;
}
struct kdtree{
	int root;LL minn;
	point t[maxn<<2];
	void updata(int x,int y){
		for(int i=0;i<m;i++){
			t[x].mn[i]=min(t[x].mn[i],t[y].mn[i]);
			t[x].mx[i]=max(t[x].mx[i],t[y].mx[i]);
		}
	}
	int build(int l,int r,int dd){
		D=dd;int mid=(l+r)>>1;
		nth_element(p+l,p+mid,p+r+1);
		for(int i=0;i<m;i++)
		t[mid].mn[i]=t[mid].mx[i]=t[mid].d[i]=p[mid].d[i];  
		t[mid].ind=mid;
		if(l<mid)t[mid].l=build(l,mid-1,(dd+1)%m);
		if(r>mid)t[mid].r=build(mid+1,r,(dd+1)%m);
		if(t[mid].l)updata(mid,t[mid].l);
		if(t[mid].r)updata(mid,t[mid].r);
		return mid;
	}	
	void init(){memset(t,0,sizeof t);root=build(1,n,0);}
	void QkNN(point p,int k){minn=1LL<<61;QkNN(root,0,p,k);}
	void QkNN(int i,int dd,point p,int k){
		int L=t[i].l,R=t[i].r;
		if(p[dd]>=t[i][dd])swap(L,R);
		if(L)QkNN(L,(dd+1)%m,p,k);
		int ok=0;LL len=dis(p,t[i]);minn=min(minn,len);
		if(Q.size()<k){Q.push(pair<LL,int>(len,i));ok=1;}
		else{
			if(len<Q.top().first)Q.pop(),Q.push(make_pair(len,i));
			if(sqr(p[dd]-t[i][dd])<Q.top().first)ok=1;
		}if(ok&&R)QkNN(R,(dd+1)%m,p,k);
	}
}T;
int main(){
	while(~scanf("%d%d",&n,&m)){
		for(int i=1;i<=n;i++)
		for(int j=0;j<m;j++)
		p[i][j]=getint();	
		T.init();
		int q=getint();
		while(q--){
			point p;int k; 
			for(int i=0;i<m;i++)p[i]=getint();k=getint();
			printf("the closest %d points are:
",k); 
			T.QkNN(p,k);int tmp[11]={0};
			while(!Q.empty()){
				tmp[++tmp[0]]=Q.top().second;
				Q.pop();
			}for(;tmp[0];tmp[0]--){
				for(int i=0;i<m;i++)
				printf("%d%c",T.t[tmp[tmp[0]]][i]," 
"[i==m-1]);
			}
		}
	}
	return 0;
}