BZOJ2626 JZPFAR

2014.12.24 15:20 Wed| 5 visits oi_2015| 2015_刷题日常| Text

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> >();
    }
}