BZOJ4520 CQOI2016K远点对（KD-Tree+堆）

　　堆维护第k大，每个点KD-Tree上A*式查询较远点，跑得飞快，复杂度玄学。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<queue>

#include<vector>

using namespace std;

#define ll long long

#define N 100010

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<''||c>'')) c=getchar();return c;}

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

int n,m,c,root,cnt;

struct point

{

    int d[];

    bool operator <(const point&a) const

    {

        return d[c]<a.d[c];

    }

}a[N];

struct KDTree{int ch[],a[][];point p;

}tree[N];

priority_queue<ll,vector<ll>,greater<ll> > q;

ll sqr(int x){return 1ll*x*x;}

ll dis(point u,point v){return sqr(u.d[]-v.d[])+sqr(u.d[]-v.d[]);}

ll dis(point u,int a[][]){return sqr(max(u.d[]-a[][],a[][]-u.d[]))+sqr(max(u.d[]-a[][],a[][]-u.d[]));}

void build(int &k,int l,int r,int op)

{

    if (l>r) return;

    k=++cnt,c=op;int mid=l+r>>;nth_element(a+l,a+mid,a+r+);

    tree[k].p=a[mid];tree[k].a[][]=tree[k].a[][]=a[mid].d[],tree[k].a[][]=tree[k].a[][]=a[mid].d[];

    for (int i=l;i<=r;i++)

    tree[k].a[][]=min(tree[k].a[][],a[i].d[]),tree[k].a[][]=max(tree[k].a[][],a[i].d[]),

    tree[k].a[][]=min(tree[k].a[][],a[i].d[]),tree[k].a[][]=max(tree[k].a[][],a[i].d[]);

    build(tree[k].ch[],l,mid-,op^);

    build(tree[k].ch[],mid+,r,op^);

}

void query(int k,point p)

{

    if (dis(tree[k].p,p)>=q.top()) q.push(dis(tree[k].p,p)),q.pop();

    int l=tree[k].ch[],r=tree[k].ch[];ll u=dis(p,tree[l].a),v=dis(p,tree[r].a);

    if (u<v) swap(l,r),swap(u,v);

    if (l&&u>=q.top()) query(l,p);

    if (r&&v>=q.top()) query(r,p);

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj4520.in","r",stdin);

    freopen("bzoj4520.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read(),m=read()<<;

    for (int i=;i<=n;i++) a[i].d[]=read(),a[i].d[]=read();

    build(root,,n,);

    while (m--) q.push();

    for (int i=;i<=n;i++) query(root,a[i]);

    cout<<q.top();

    return ;

}