萌新$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";
        }
    }
}