解题关键:模板题(结合起来了)
#include#include #include #include #include #include #include #define N 50050#define inf (1<<30)#define sq(x) (x)*(x)using namespace std;int n,m,dim,rt,k;struct node{ int p[10],minn[10],maxx[10]; bool operator<(const node &u)const{ return p[dim] PDN;priority_queue que;struct kd_tree{ int c[N][2]; node s[N],q; void update(int o){ //管辖范围 int l=c[o][0],r=c[o][1]; for(int i=0;i t.p[i])tmp+=sq(s[o].minn[i]-t.p[i]); if(t.p[i]>s[o].maxx[i])tmp+=sq(t.p[i]-s[o].maxx[i]); } return tmp; } void build(int &o,int l,int r,int now){ o=(l+r)>>1;now%=k;dim=now; nth_element(a+l,a+o,a+r+1); add(o,a[o]); if(l!=o) build(c[o][0],l,o-1,now+1); if(o!=r) build(c[o][1],o+1,r,now+1); update(o); } void ins(int o,int now){ now%=k; if(q.p[now] tmp.first){ que.pop(); que.push(tmp); } } int dl=c[o][0]?dist(q,c[o][0]):inf,dr=c[o][1]?dist(q,c[o][1]):inf; if(dl0;i--){ for(int j=0;j