传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3053
既然 @nilihan1999 神犇一直不更新kdtree就只好自己学了……
写完果然没有nilihan1999快= = 、
而且不太明白如何判断是否进入另一个子树
nilihan1999神犇如果看到了求讲
#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:\n",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]," \n"[i==m-1]);
}
}
}
return 0;
}