BZOJ2626 JZPFAR
Solution
将之前的K-D Tree中的答案变量换成优先队列即可。注意priority_queue默认是大根堆。询问时需要保证堆中元素个数为K,堆内元素个数小于K时也需要搜索估价较近的子树。另外这道题需要用到long long保存距离。时间复杂度为 $\mathcal O(m\sqrt n\logk)$ 。
Code
#include <bits/stdc++.h> using namespace std; #define N 100005 #define inf 0x3f3f3f3f #define sqr(x) ((x)*(x)) #define lson(x) (x->ch[0]) #define rson(x) (x->ch[1]) #define son(x,d) (x->ch[d]) inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int pos; struct point { long long id,x,y; point(){} point(int _id):id(_id),x(read()),y(read()) {} bool operator <(const point &p) const { return pos?y<p.y:x<p.x; } inline friend ostream &operator <<(ostream &out, const point &p) { out<<'('<<p.x<<','<<p.y<<')'; return out; } inline friend long long dist(const point &p1,const point &p2) { return sqr(p1.x-p2.x)+sqr(p1.y-p2.y); } }; struct kdtree { point p; kdtree *ch[2]; long long l,r,u,d; kdtree(){} kdtree(const point &_p):p(_p) { l=r=_p.x; u=d=_p.y; } void *operator new(size_t size); inline void update(int c) { l=min(l,ch[c]->l); r=max(r,ch[c]->r); u=max(u,ch[c]->u); d=min(d,ch[c]->d); } inline long long maxdist(const point &_p) { return max(sqr(_p.x-l),sqr(_p.x-r))+max(sqr(_p.y-u),sqr(_p.y-d)); } }newnode[N],*null=new kdtree(); void *kdtree::operator new(size_t size) { static kdtree *P=newnode; return P++; } int n,m; point p[N]; kdtree *build(int l,int r,int _pos=0) { if(l>r) return null; pos=_pos; int mid=(l+r)>>1; nth_element(p+l,p+mid,p+r+1); kdtree *re=new kdtree(p[mid]); lson(re)=build(l,mid-1,_pos^1); rson(re)=build(mid+1,r,_pos^1); if(lson(re)!=null) re->update(0); if(rson(re)!=null) re->update(1); return re; } void insert(kdtree* &root,point p,int _pos=0) { if(root==null) { root=new kdtree(p); lson(root)=rson(root)=null; return; } pos=_pos; if(p<root->p) insert(lson(root),p,_pos^1), root->update(0); else insert(rson(root),p,_pos^1), root->update(1); } priority_queue< pair<long long,int> > q; void querymax(kdtree *root,point p,int k) { q.push(make_pair(-dist(p,root->p),root->p.id)); while((int)q.size()>k) q.pop(); long long dist[2]={lson(root)==null?-inf:lson(root)->maxdist(p), rson(root)==null?-inf:rson(root)->maxdist(p)}; int d=dist[0]<dist[1]; if(son(root,d)!=null) querymax(son(root,d),p,k); if(son(root,d^1)!=null&&((int)q.size()<k||-q.top().first<dist[d^1])) querymax(son(root,d^1),p,k); } int main() { cin>>n; for(int i=1;i<=n;i++) p[i]=point(i); kdtree *root=build(1,n); cin>>m; for(int i=1;i<=m;i++) { point p(0); int k=read(); querymax(root,p,k); printf("%d\n",q.top().second); q=priority_queue< pair<long long,int> >(); } }