Lvat_s Blog

KD-Tree 模版题

查询最近点在KD树上走一走就行了

注意：此题不需要特别的卡常技巧，基本上写对了就过了(不需要重构子树、加一些玄学科技)

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
 
const int N=500005,INF=2100000000;
 
int n,m,Sort_Tag,root,ans=INF;
 
struct KDTree{
int l,r,d[2],mn[2],mx[2];
KDTree(){}
KDTree(int x,int y){mn[0]=mx[0]=d[0]=x;mn[1]=mx[1]=d[1]=y;l=r=0;}
friend bool operator<(KDTree A,KDTree B){return A.d[Sort_Tag]<B.d[Sort_Tag];}
}tree[N<<2],Temp;
 
int Abs(int x){return x>0?x:-x;}
int Dist(KDTree A,KDTree B){return Abs(A.d[0]-B.d[0])+Abs(A.d[1]-B.d[1]);}
 
void Pushup(int rt){
if(tree[rt].l){
    tree[rt].mx[0]=max(tree[rt].mx[0],tree[tree[rt].l].mx[0]);
    tree[rt].mx[1]=max(tree[rt].mx[1],tree[tree[rt].l].mx[1]);
    tree[rt].mn[0]=min(tree[rt].mn[0],tree[tree[rt].l].mn[0]);
    tree[rt].mn[1]=min(tree[rt].mn[1],tree[tree[rt].l].mn[1]);
}
if(tree[rt].r){
    tree[rt].mx[0]=max(tree[rt].mx[0],tree[tree[rt].r].mx[0]);
    tree[rt].mx[1]=max(tree[rt].mx[1],tree[tree[rt].r].mx[1]);
    tree[rt].mn[0]=min(tree[rt].mn[0],tree[tree[rt].r].mn[0]);
    tree[rt].mn[1]=min(tree[rt].mn[1],tree[tree[rt].r].mn[1]);
}
}
 
int Build(int l,int r,int D){
Sort_Tag=D;
int mid=l+r>>1;
nth_element(tree+l,tree+mid,tree+r+1);
tree[mid].mn[0]=tree[mid].mx[0]=tree[mid].d[0];
tree[mid].mn[1]=tree[mid].mx[1]=tree[mid].d[1];
if(l<mid)tree[mid].l=Build(l,mid-1,!D);
if(r>mid)tree[mid].r=Build(mid+1,r,!D);
Pushup(mid);
return mid;
}
 
void _Insert(int rt,int D){
if(Temp.d[D]>=tree[rt].d[D]){
    if(tree[rt].r)_Insert(tree[rt].r,!D);
    else {tree[rt].r=++n;tree[n]=Temp;}
}
else {
    if(tree[rt].l)_Insert(tree[rt].l,!D);
    else {tree[rt].l=++n;tree[n]=Temp;}
}
Pushup(rt);
}
 
void Insert(int x,int y){
Temp=KDTree(x,y);
_Insert(root,0);
}
 
int MxDist(int rt,int x,int y){
return max(tree[rt].mn[0]-x,0)+max(x-tree[rt].mx[0],0)+max(tree[rt].mn[1]-y,0)+max(y-tree[rt].mx[1],0);
}
 
void _Query(int rt){
int Dl=INF,Dr=INF,Dm=Dist(tree[rt],Temp);
ans=min(ans,Dm);
if(tree[rt].l)Dl=MxDist(tree[rt].l,Temp.d[0],Temp.d[1]);
if(tree[rt].r)Dr=MxDist(tree[rt].r,Temp.d[0],Temp.d[1]);
if(Dl<Dr){
    if(Dl<ans)_Query(tree[rt].l);
    if(Dr<ans)_Query(tree[rt].r);
}
else {
    if(Dr<ans)_Query(tree[rt].r);
    if(Dl<ans)_Query(tree[rt].l);
}
}
 
int Query(int x,int y){
Temp=KDTree(x,y);ans=INF;
_Query(root);
return ans;
}

int main(){
freopen("2648.in","r",stdin);
freopen("2648.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d %d",&tree[i].d[0],&tree[i].d[1]);
root=Build(1,n,0);
for(int i=1;i<=m;i++){
    int opt,x,y;
    scanf("%d %d %d",&opt,&x,&y);
    if(opt==1)Insert(x,y);
    if(opt==2)printf("%d\n",Query(x,y));
}
return 0;
}