萌新$deco$今天终于学习了$k-d\ tree$
具体操作包含,建树,插入以及查询最近点
$k-d\ tree$建树的时候和平衡树类似,即尽量使两边平分,但如果割的太长会导致效率降低,如下图
所以说应该修改算法,我们依次分割$x$轴和$y$轴
这样就能提升很多效率
然后对于求最近点,我们的估价函数是两点间的曼哈顿距离,这个可以在$k-d\ tree$中直接计算,
但是如果多次插入,很可能导致$k-d\ tree$不再平衡,我们就可以设定一个平衡因子,当一个儿子$size$过大时我们就重构
然后就完了qwq
放个代码8
/*deco loves Chino*/
#include <bits/stdc++.h>
using namespace std;
const double al=0.65;
int wd;
struct point
{
int x[2];
bool operator<(const point &a)
{
return x[wd]<a.x[wd];
}
}p[1000010];
struct node
{
int mi[2],mx[2],ls,rs,sz;
point tp;
}t[1000010];
int n,m,rt,cnt,top,ans,can[1000010];
int newnode()
{
if(top)
{
return can[top--];
}
else
{
return ++cnt;
}
}
void pushup(int k)
{
int l=t[k].ls,r=t[k].rs;
for(int i=0;i<=1;i++)
{
t[k].mi[i]=t[k].mx[i]=t[k].tp.x[i];
if(l)
{
t[k].mi[i]=min(t[k].mi[i],t[l].mi[i]);
t[k].mx[i]=max(t[k].mx[i],t[l].mx[i]);
}
if(r)
{
t[k].mi[i]=min(t[k].mi[i],t[r].mi[i]);
t[k].mx[i]=max(t[k].mx[i],t[r].mx[i]);
}
}
t[k].sz=t[l].sz+t[r].sz+1;
}
int build(int l,int r,int qaq)
{
if(l>r)
{
return 0;
}
int k=newnode(),mid=(l+r)>>1;
wd=qaq,nth_element(p+l,p+mid,p+r+1);
t[k].tp=p[mid];
t[k].ls=build(l,mid-1,qaq^1),t[k].rs=build(mid+1,r,qaq^1);
pushup(k);
return k;
}
void rebuild(int k,int num)
{
if(t[k].ls)
{
rebuild(t[k].ls,num);
}
p[num+t[t[k].ls].sz+1]=t[k].tp,can[++top]=k;
if(t[k].rs)
{
rebuild(t[k].rs,num+t[t[k].ls].sz+1);
}
}
void check(int &k,int qaq)
{
if(al*t[k].sz<t[t[k].ls].sz||al*t[k].sz<t[t[k].rs].sz)
{
rebuild(k,0);
k=build(1,t[k].sz,qaq);
}
}
void ins(point tmp,int &k,int qaq)
{
if(!k)
{
k=newnode(),t[k].tp=tmp,t[k].ls=t[k].rs=0;
pushup(k);
return ;
}
if(t[k].tp.x[qaq]<tmp.x[qaq])
{
ins(tmp,t[k].rs,qaq^1);
}
else
{
ins(tmp,t[k].ls,qaq^1);
}
pushup(k);
check(k,qaq);
}
int getdis(point tmp,int k)
{
int qwq=0;
for(int i=0;i<=1;i++)
{
qwq+=max(0,tmp.x[i]-t[k].mx[i])+max(0,t[k].mi[i]-tmp.x[i]);
}
return qwq;
}
int dist(point a,point b)
{
return abs(a.x[0]-b.x[0])+abs(a.x[1]-b.x[1]);
}
void query(point tmp,int k)
{
ans=min(ans,dist(tmp,t[k].tp));
int dl=0x7FFFFFFF,dr=0x7FFFFFFF;
if(t[k].ls)
{
dl=getdis(tmp,t[k].ls);
}
if(t[k].rs)
{
dr=getdis(tmp,t[k].rs);
}
if(dl<dr)
{
if(dl<ans)
{
query(tmp,t[k].ls);
}
if(dr<ans)
{
query(tmp,t[k].rs);
}
}
else
{
if(dr<ans)
{
query(tmp,t[k].rs);
}
if(dl<ans)
{
query(tmp,t[k].ls);
}
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
scanf("%d%d",&p[i].x[0],&p[i].x[1]);
}
rt=build(1,n,0);
for(int i=1;i<=m;i++)
{
point tmp;
int opt;
scanf("%d%d%d",&opt,&tmp.x[0],&tmp.x[1]);
if(opt==1)
{
ins(tmp,rt,0);
}
else
{
ans=0x7FFFFFFF;
query(tmp,rt);
cout<<ans<<"\n";
}
}
}