同样是KDT，为什么我的TLE得这么惨？求助

#include <iostream>
#include <algorithm>
#include <cmath>
#include <fstream>
using namespace std;

const int INF=1e9;
const int maxn=600005;
const double a=0.725;

inline int read()
{
	int s=0;char c=getchar();
	while (c<'0'||c>'9')
	{
		c=getchar();
	}
	while (c>='0'&&c<='9')
	{
		s=s*10+c-'0';
		c=getchar();
	}
	return s;
}
struct point
{
	int x,y;
};
point p[maxn];
int n,m,ans;
int g[maxn],tot,rt,op,X,Y;
int L[maxn],R[maxn],U[maxn],D[maxn],d[maxn],lc[maxn],rc[maxn],siz[maxn];

inline void print(int x)
{
	if (!x)
	{
		return;
	}
	print(lc[x]);
	g[++tot]=x;
	print(rc[x]);
}
bool cmp1(int a,int b)
{
	return p[a].x<p[b].x;
} 
bool cmp2(int a,int b)
{
	return p[a].y<p[b].y;
} 

inline void maintain(int x)
{
	siz[x]=1;
	L[x]=R[x]=p[x].x;U[x]=D[x]=p[x].y;
	if (lc[x])
	{
		siz[x]+=siz[lc[x]];
		L[x]=min(L[x],L[lc[x]]);
		R[x]=max(R[x],R[lc[x]]);
		U[x]=max(U[x],U[lc[x]]);
		D[x]=min(D[x],D[lc[x]]);
	}
	if (rc[x])
	{
		siz[x]+=siz[rc[x]];
		L[x]=min(L[x],L[rc[x]]);
		R[x]=max(R[x],R[rc[x]]);
		U[x]=max(U[x],U[rc[x]]);
		D[x]=min(D[x],D[rc[x]]);
	}
}

inline int build(int l,int r)
{
	if (l>r)
	{
		return 0;
	}
	int mid=(l+r)>>1;
	double avx=0,avy=0,vax=0,vay=0;
	for (register int i=l;i<=r;i++)
	{
		avx+=p[g[i]].x;avy+=p[g[i]].y;
	}
	avx/=(double)(r-l+1);avy/=(double)(r-l+1);
	for (register int i=l;i<=r;i++)
	{
		vax+=abs(p[g[i]].x-avx);
		vay+=abs(p[g[i]].y-avy);
	}
	if (vax>vay)
	{ 
		nth_element(g+l,g+mid,g+r+1,cmp1);
		d[g[mid]]=1;
	}
	else
	{
		nth_element(g+l,g+mid,g+r+1,cmp2);
		d[g[mid]]=2;
	}
	lc[g[mid]]=build(l,mid-1);
	rc[g[mid]]=build(mid+1,r);
	maintain(g[mid]);
	return g[mid];
}

void rebuild(int &x)
{
	tot=0;
	print(x);
	x=build(1,tot);
}
bool bad(int x)
{
	return siz[x]*a<=(double)max(siz[lc[x]],siz[rc[x]]);
}


void ins(int &x,int id)
{
	if (!x)
	{
		x=id;
		maintain(x);
		return;
	}
	if (d[x]==1)
	{
		if (p[id].x<=p[x].x)
		{
			ins(lc[x],id);
		}
		else
		{
			ins(rc[x],id);
		}
	}
	else
	{
		if (p[id].y<=p[x].y)
		{
			ins(lc[x],id);
		}
		else
		{
			ins(rc[x],id);
		}
	}
	maintain(x);
	if (bad(x))
	{
		rebuild(x);
 
	}
}
int dis(int id)
{
	return abs(p[id].x-X)+abs(p[id].y-Y);
}
int f(int id)
{
	int ret=0;
	if (L[id]>X)
	{
		ret+=L[id]-X;
	}
	else if (R[id]<X);
	{
		ret+=X-R[id];
	}
	if (D[id]>Y)
	{
		ret+=D[id]-Y;
	}
	else if (U[id]<Y);
	{
		ret+=Y-U[id];
	}
	return ret;
}
inline void query(int u)
{
	if (!u)
	{
		return;
	}
	ans=min(ans,dis(u));
	int disl=f(lc[u]),disr=f(rc[u]);
	if (disl<disr)
	{
		if (disl<ans)
		{
			query(lc[u]);
		}
		if (disr<ans)
		{
			query(rc[u]);
		}
	}
	else
	{
		if (disr<ans)
		{
			query(rc[u]);
		}
		if (disl<ans)
		{
			query(lc[u]);
		}
	}
}
int main()
{
	//freopen("P.in","r",stdin);
	//freopen("KDT.out","w",stdout);
	n=read();m=read();
	for (register int i=1;i<=n;i++)
	{
		p[i].x=read();p[i].y=read();
		g[i]=i;
	}
	rt=build(1,n);
	for (register int i=1;i<=m;i++)
	{
		op=read();X=read();Y=read();
		if (op==1)
		{
			p[++n].x=X;
			p[n].y=Y;
			ins(rt,n);
		}
		else 
		{
			ans=INF;
			query(rt);
			cout<<ans<<endl;
		}
	}
}

#include<bits/stdc++.h>
#define il inline
using namespace std;
namespace io{static streambuf *inbuf=cin.rdbuf();static streambuf *outbuf=cout.rdbuf();char buf[1<<21],*p1=buf,*p2=buf;inline char gc(){return (p1==p2&&(p2=(p1=buf)+inbuf->sgetn(buf,1<<21),p1==p2)?EOF:*p1++);}inline void pc(const char x){static streambuf *outbuf=cout.rdbuf();outbuf->sputc(x);}inline void ps(const char *x){unsigned _len=strlen(x);for(unsigned i=0;i<_len;i++)pc(x[i]);}inline int read(){register int _s=0,_f=1;register char _ch=gc();for(;!isdigit(_ch);_ch=gc())if(_ch=='-')_f=-1;for(;isdigit(_ch);_ch=gc())_s=_s*10+_ch-'0';return _s*_f;}template<typename T>inline void write(T _x1){if(_x1<0)pc('-'),_x1=-_x1;static char _sta[15];int _p=0;do{_sta[_p++]=_x1%10^48;_x1/=10;}while(_x1);while(_p--)pc(_sta[_p]);}string _s;inline string readstr(){_s.clear();register char _ch=gc();while(isspace(_ch))_ch=gc();for(;!isspace(_ch);_ch=gc())_s+=_ch;return _s;}inline void writestr(const string _s){for(unsigned i=0;i<_s.size();++i)pc(_s[i]);}template<typename T>inline void writeln(const T _x){write(_x);pc(10);}template<typename T>inline void writesp(const T _x){write(_x);pc(' ');}}using namespace io;
const int maxn=6e5+5;
int n,m,now,ls[maxn],rs[maxn],rt,mxx[maxn],mxy[maxn],mnx[maxn],mny[maxn],siz[maxn],ans=1e9;
bool d[maxn];
struct node{
	int x,y;
}a[maxn];
il void pushup(int u){
	mxx[u]=max(mxx[u],mxx[now]);mxy[u]=max(mxy[u],mxy[now]);
	mnx[u]=min(mnx[u],mnx[now]);mny[u]=min(mny[u],mny[now]);
}
il int dis(int u){
	return abs(a[now].x-a[u].x)+abs(a[now].y-a[u].y);
}
il int mindis(int u){
    int res=0;
    if(mnx[u]>a[now].x||a[now].x>mxx[u])res+=mnx[u]>a[now].x?mnx[u]-a[now].x:a[now].x-mxx[u];
    if(mny[u]>a[now].y||a[now].y>mxy[u])res+=mny[u]>a[now].y?mny[u]-a[now].y:a[now].y-mxy[u];
    return res;
}
void ask(int u){
    if(!u)return;
    ans=min(ans,dis(u));
    int l=mindis(ls[u]),r=mindis(rs[u]);
    if(l<r){
        if(l<ans)ask(ls[u]);
        if(r<ans)ask(rs[u]);
    }else{
        if(r<ans)ask(rs[u]);
        if(l<ans)ask(ls[u]);
    }
}
il double sqr(double x){return x*x;}
bool dcmp;
int g[maxn],tot;
il bool cmp(int p,int q){
    if(dcmp)return a[p].x<a[q].x;
    return a[p].y<a[q].y;
}
int build(int l,int r){
    if(l>r)return 0;
    int mid=(l+r)/2;
    double avx=0,avy=0,vax=0,vay=0;
    for(int i=l;i<=r;i++)
        avx+=a[g[i]].x,avy+=a[g[i]].y;
    avx/=1.0*(r-l+1);avy/=1.0*(r-l+1);
    for(int i=l;i<=r;i++)
        vax+=sqr(a[g[i]].x-avx),vay+=sqr(a[g[i]].y-avy);
    dcmp=d[g[mid]]=(vax>vay);nth_element(g+l,g+mid,g+r+1,cmp);
    ls[g[mid]]=build(l,mid-1);rs[g[mid]]=build(mid+1,r);
    mxx[g[mid]]=mnx[g[mid]]=a[g[mid]].x;
    mxy[g[mid]]=mny[g[mid]]=a[g[mid]].y;
    siz[g[mid]]=1;
    if(ls[g[mid]])now=ls[g[mid]],pushup(g[mid]),siz[g[mid]]+=siz[ls[g[mid]]];
    if(rs[g[mid]])now=rs[g[mid]],pushup(g[mid]),siz[g[mid]]+=siz[rs[g[mid]]];
    return g[mid];
}
void print(int u){
    if(!u)return;
    print(ls[u]);
    g[++tot]=u;
    print(rs[u]);
}
il void rebuild(int &u){
    tot=0;print(u);
    u=build(1,tot);
}
il bool bad(int u){
    return 0.725*siz[u]<=1.0*max(siz[ls[u]],siz[rs[u]]);
}
void ins(int &u,bool op){
	if(!u)return u=now,siz[u]=1,void();
	if(!op)ins(a[now].x<=a[u].x?ls[u]:rs[u],!d[u]);
	else ins(a[now].y<=a[u].y?ls[u]:rs[u],!d[u]);
	pushup(u);siz[u]=siz[ls[u]]+siz[rs[u]]+1;
    int tmp=now;if(bad(u))rebuild(u);now=tmp;
}
int main(){
    srand(time(0));
	n=read();m=read();
	for(int i=1;i<=n;i++)
        a[i].x=read(),a[i].y=read(),g[i]=i;
    rt=build(1,n);now=n;
    int op,tmp,x,y;
    while(m--){
        op=read();x=read();y=read();
        if(op==1){
            a[++now]=(node){x,y};
            mxx[now]=mnx[now]=a[now].x;
            mxy[now]=mny[now]=a[now].y;
            ins(rt,d[rt]);
        }else{
            tmp=now;
            a[now=0]=(node){x,y};
            ans=1e9;ask(rt);
            writeln(ans);
            now=tmp;
        }
    }
	return 0;
}