BZOJ4520：[CQOI2016]K远点对

浅谈\(K-D\) \(Tree\)：https://www.cnblogs.com/AKMer/p/10387266.html

题目传送门：https://lydsy.com/JudgeOnline/problem.php?id=4520

说实话，写了这个题之后我才明白\(K-D\) \(Tree\)最优美的地方。

那就是剪枝。

用堆维护前\(2k\)远的点对，如果当前子树内里询问点最远的距离都比堆顶小那么就直接退出。

时间复杂度：\(O(nlogn)\)

空间复杂度：\(O(n)\)

代码如下：

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
#define sqr(x) (1ll*(x)*(x))

const int maxn=1e5+5,inf=2147483647;

int n,k,pps,X,Y;

int read() {
    int x=0,f=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
    return x*f;
}

struct heap {
    int tot;
    ll tree[maxn];

    void ins(ll v) {
        tree[++tot]=v;int pos=tot;
        while(pos>1) {
            if(tree[pos]<tree[pos>>1])
                swap(tree[pos],tree[pos>>1]),pos>>=1;
            else break;
        }
    }

    void pop() {
        tree[1]=tree[tot--];
        int pos=1,son=2;
        while(son<=tot) {
            if(son<tot&&tree[son|1]<tree[son])son|=1;
            if(tree[son]<tree[pos])
                swap(tree[pos],tree[son]),pos=son,son=pos<<1;
            else break;
        }
    }
}H;

struct kd_tree {
    int root;

    struct point {
        int ls,rs;
        int c[2],mn[2],mx[2];

        bool operator<(const point &a)const {
            return c[pps]<a.c[pps];
        }
    }p[maxn];

    int build(int l,int r,int d) {
        int mid=(l+r)>>1,u=mid;pps=d;
        nth_element(p+l,p+mid,p+r+1);
        if(l<mid)p[u].ls=build(l,mid-1,d^1);
        if(r>mid)p[u].rs=build(mid+1,r,d^1);
        int ls=p[u].ls,rs=p[u].rs;
        for(int i=0;i<2;i++) {
            int mn=min(p[ls].mn[i],p[rs].mn[i]);
            p[u].mn[i]=min(p[u].c[i],mn);
            int mx=max(p[ls].mx[i],p[rs].mx[i]);
            p[u].mx[i]=max(p[u].c[i],mx);
        }
        return u;
    }

    void prepare() {
        p[0].mn[0]=p[0].mn[1]=inf;
        p[0].mx[0]=p[0].mx[1]=-inf;
        for(int i=1;i<=n;i++)
            p[i].c[0]=read(),p[i].c[1]=read();
        root=build(1,n,0);
    }

    ll dis(int u) {
        ll a=max(abs((ll)p[u].mn[0]-X),abs((ll)p[u].mx[0]-X));
        ll b=max(abs((ll)p[u].mn[1]-Y),abs((ll)p[u].mx[1]-Y));
        return sqr(a)+sqr(b);
    }

    void query(int u) {
        if(!u)return;
        if(H.tot==k&&dis(u)<H.tree[1])return;
        ll dist=sqr(abs((ll)X-p[u].c[0]))+sqr(abs((ll)Y-p[u].c[1]));
        if(H.tot!=k||dist>H.tree[1]) {
            H.ins(dist);if(H.tot>k)H.pop();
        }
        ll dl=p[u].ls?dis(p[u].ls):-sqr(inf);
        ll dr=p[u].rs?dis(p[u].rs):-sqr(inf);
        if(dl>dr)query(p[u].ls),query(p[u].rs);
        else query(p[u].rs),query(p[u].ls);
    }
}T;

int main() {
    n=read(),k=read()<<1;
    T.prepare();
    for(int i=1;i<=n;i++)
        X=T.p[i].c[0],Y=T.p[i].c[1],T.query(T.root);
    printf("%lld\n",H.tree[1]);
    return 0;
}

BZOJ4520：[CQOI2016]K远点对

原文：https://www.cnblogs.com/AKMer/p/10414499.html