\(\color{purple}\text{P4169 [Violet]天使玩偶/SJY摆棋子}\)
以本题为例题讲解模板怎么写。
思路
\(\text{K-D Tree}\) 是一种类二叉查找树，不过元素是多维的，所以每次对于子树的划分也是依据不同维度的。
本题使用二维的 \(\text{K-D Tree}\) ，这样每次将图分成左右子树其实就是将图划分成两个矩形。我们求出每棵子树表示的矩形（即记录其中点的最大最小 \(x,y\) 值），然后判断查询点时，每次走到一个点，看看目前划分的左右矩阵到目前点的距离是否小于目前最优解，如果成立就往那走。
建树
最基本操作，实现给定一堆点，将他们建成一棵 \(\text{K-D Tree}\) 。每次找到剩下的点的中点，把小的点放左边，大的点放右边。
重构
当树高过大时，我们需要对整棵树拍扁重构。把重构的子树中的点放入数组，删除（小心不要删太早了），在重新建树。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=3e6+1110,inf=2e9;
const double alph=0.75;
int read(){
int x=0,f=1;char c=getchar();
while(c>'9' || c<'0'){if(c=='-')f=-1;c=getchar();}
while(c>='0' && c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return x*f;
}
int n,m,rna,qans;
struct Point{
int w[2];bool operator<(const Point &A)const{return w[rna]<A.w[rna];}
}tp[N];
struct KDTree{
int cyx[N],top;
int cnt,rt;
int ls[N],rs[N],sze[N];
Point minv[N],maxv[N],p[N];
int newnode(){if(top)return cyx[top--];return ++cnt;}
void pushup(int u){
sze[u]=sze[ls[u]]+sze[rs[u]]+1;
for(int i=0;i<=1;i++){
minv[u].w[i]=maxv[u].w[i]=p[u].w[i];
if(ls[u])minv[u].w[i]=min(minv[u].w[i],minv[ls[u]].w[i]),maxv[u].w[i]=max(maxv[u].w[i],maxv[ls[u]].w[i]);
if(rs[u])minv[u].w[i]=min(minv[u].w[i],minv[rs[u]].w[i]),maxv[u].w[i]=max(maxv[u].w[i],maxv[rs[u]].w[i]);
}
}
void build(int &u,int l,int r,int kd){
if(l>r)return;
u=newnode();int mid=(l+r)>>1;
rna=kd;nth_element(tp+l,tp+mid,tp+r+1);p[u]=tp[mid];ls[u]=rs[u]=0;
build(ls[u],l,mid-1,kd^1);build(rs[u],mid+1,r,kd^1);
pushup(u);return;
}
void pia(int u,int l){
if(ls[u])pia(ls[u],l);
tp[l+sze[ls[u]]+1]=p[u],cyx[++top]=u;
if(rs[u])pia(rs[u],l+sze[ls[u]]+1);
return;
}
void check(int &u,int wd){
if(sze[ls[u]]>alph*sze[u] || sze[rs[u]]>alph*sze[u]){
pia(u,0);build(u,1,sze[u],wd);
}
return;
}//重构
void insert(int &u,int kd,Point t){
if(!u){u=newnode();p[u]=t;ls[u]=rs[u]=0;pushup(u);return;}
if(t.w[kd]<p[u].w[kd])insert(ls[u],kd^1,t);
else insert(rs[u],kd^1,t);
pushup(u);check(u,kd);
}
int getdis(int u,Point t){
int res=0;
for(int i=0;i<=1;i++)
res+=max(0,t.w[i]-maxv[u].w[i])+max(0,minv[u].w[i]-t.w[i]);
return res;//查点到矩阵的距离
}
void query(int u,Point t){
qans=min(qans,abs(p[u].w[0]-t.w[0])+abs(p[u].w[1]-t.w[1]));
int dl=inf,dr=inf;
if(ls[u])dl=getdis(ls[u],t);
if(rs[u])dr=getdis(rs[u],t);
if(dl<dr){
if(dl<qans)query(ls[u],t);
if(dr<qans)query(rs[u],t);
}
else{
if(dr<qans)query(rs[u],t);
if(dl<qans)query(ls[u],t);
}//优先查靠得近的子树
return;
}
void bark(int u){
cout<<p[u].w[0]<<" "<<p[u].w[1]<<" "<<minv[u].w[0]<<" "<<minv[u].w[1]<<" "<<maxv[u].w[0]<<" "<<maxv[u].w[1]<<endl;
cout<<ls[u]<<" "<<rs[u]<<endl;
if(ls[u])bark(ls[u]);
if(rs[u])bark(rs[u]);
return;
}
void BK(){
for(int i=1;i<=top;i++)
cout<<cyx[i]<<" ";cout<<endl;
cout<<"-----------------------------"<<endl;
bark(rt);
cout<<"-----------------------------"<<endl;
}
}T;
int main(){
n=read(),m=read();
for(int i=1;i<=n;i++)tp[i].w[0]=read(),tp[i].w[1]=read();
T.build(T.rt,1,n,0);
for(int i=1;i<=m;i++){
int opt=read();
Point tmp;tmp.w[0]=read(),tmp.w[1]=read();
if(opt==1)T.insert(T.rt,0,tmp);
else{
qans=inf;//ans是全局记录的
T.query(T.rt,tmp);
printf("%d\n",qans);
}
}
return 0;
}