题意

一个k维空间，给出n个点的坐标，给出t个询问，每个询问给出一个点的坐标和一个m。对于每个询问找出跟这个点最接近的m个点

分析

 kd树的模板题。

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             6   7 using namespace std;  8 typedef long long LL;  9 const int maxn=50080; 10 const int K=5; 11 int num,nownum,m; 12 LL ans; 13 struct kdNode{ 14     LL x[K]; 15     int div; 16     bool lef; 17 }Ans[12]; 18 struct Node{ 19     kdNode a; 20     LL dis; 21     bool operator <(const Node &a)const{ 22         return dis
           
            b?a:b; 36 } 37 kdNode p[maxn],q; 38 LL dis(kdNode a,kdNode b,int k){ 39 LL res=0; 40 for(int i=0;i
            
             qq; 46 void buildKD(int l,int r,kdNode* p,int d,int k){ 47 if(l>r)return ; 48 int m=(l+r)/2; 49 cmpNo=d; 50 nth_element(p+l,p+m,p+r+1,cmp); 51 p[m].div=d; 52 if(l==r){ 53 p[m].lef=1; 54 return ; 55 } 56 buildKD(l,m-1,p,(d+1)%k,k); 57 buildKD(m+1,r,p,(d+1)%k,k); 58 } 59 void findkd(int l,int r,kdNode& tar,kdNode* p,int k){ 60 if(l>r)return; 61 int m=(l+r)/2; 62 LL d=dis(p[m],tar,k); 63 if(p[m].lef){ 64 if(nownum
             
              d){ 70 qq.pop(); 71 qq.push(Node(p[m],d)); 72 ans=qq.top().dis; 73 } 74 return; 75 } 76 LL t=tar.x[p[m].div]-p[m].x[p[m].div]; 77 if(t>0){ 78 findkd(m+1,r,tar,p,k); 79 if(nownum
              
               d){ 86 qq.pop(); 87 qq.push(Node(p[m],d)); 88 ans=qq.top().dis; 89 } 90 if(ans>t*t) 91 findkd(l,m-1,tar,p,k); 92 } 93 }else{ 94 findkd(l,m-1,tar,p,k); 95 if(nownum
               
                d){102 qq.pop();103 qq.push(Node(p[m],d));104 ans=qq.top().dis;105 }106 if(ans>t*t){107 findkd(m+1,r,tar,p,k);108 }109 }110 }111 }112 113 int n,k;114 int main(){115 while(scanf("%d%d",&n,&k)==2){116 for(int i=0;i
                
                 =1;j--){140 for(int kk=0;kk