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