(KD-tree)做最近点对的复杂度好像是假的吧，怎么看也看不出来是(O(sqrt{n}))啊
首先(KD-tree)长得和平衡树还是很像的，每个节点都存储了一个(k)维空间上的点
但是(KD-tree)的每一棵子树都是一个(k)维的空间，对于(2D-tree)来说就是一个矩形
我们存好这个矩形的内最小和最大的的(x,y)坐标，就可以利用这个东西来剪枝了
如果发现询问点和矩形的曼哈顿距离都超过了当前答案，我们就没有必要进入这个子树了
由于这道题还有插入，我们往某一个位置反复插入可能会导致树高过大，于是自闭
可以利用替罪羊的思想，对于一个点(x)，发现(max(sz[l[x]],sz[r[x]])>sz[x] imes alpha)，就说明这个子树很不平衡了，我们就暴力重构一下，(alpha)一般取(0.65)到(0.75)就好
代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define re register
#define LL long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
const int maxn=1000005;
const int inf=99999999;
const double alph=0.75;
inline int read() {
char c=getchar();int x=0;while(c<'0'||x>'9') c=getchar();
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
int n,m,cnt,op,ans,top;
int mx[maxn][2],mi[maxn][2],sz[maxn],st[maxn];
int l[maxn],r[maxn];
struct Point{int x[2];}p[maxn],id[maxn];
inline int newNode() {
if(top) return st[top--];
return ++cnt;
}
inline int cmp(Point A,Point B) {return A.x[op]<B.x[op];}
inline void pushup(int k) {
mi[k][0]=mx[k][0]=id[k].x[0];
mi[k][1]=mx[k][1]=id[k].x[1];
for(re int i=0;i<2;i++) {
if(l[k]) mi[k][i]=min(mi[k][i],mi[l[k]][i]),
mx[k][i]=max(mx[k][i],mx[l[k]][i]);
if(r[k]) mi[k][i]=min(mi[k][i],mi[r[k]][i]);
mx[k][i]=max(mx[k][i],mx[r[k]][i]);
}
sz[k]=sz[l[k]]+sz[r[k]]+1;
}
int build(int x,int y,int o) {
if(x>y) return 0;
int now=newNode();
int mid=x+y>>1;
op=o;std::nth_element(p+x,p+mid,p+y+1,cmp);id[now]=p[mid];
l[now]=build(x,mid-1,o^1);r[now]=build(mid+1,y,o^1);
pushup(now);return now;
}
inline int getdis(Point a,int k) {
int res=0;
for(re int i=0;i<2;i++) {
if(a.x[i]>=mi[k][i]&&a.x[i]<=mx[k][i]) continue;
if(a.x[i]<=mi[k][i]) res+=mi[k][i]-a.x[i];
else if(a.x[i]>=mx[k][i]) res+=a.x[i]-mx[k][i];
}
return res;
}
inline int dis(Point a,Point b) {return abs(a.x[0]-b.x[0])+abs(a.x[1]-b.x[1]);}
void query(Point now,int k) {
ans=min(ans,dis(now,id[k]));
int dl=inf,dr=inf;
if(l[k]) dl=getdis(now,l[k]);
if(r[k]) dr=getdis(now,r[k]);
if(dl<dr) {
if(dl<ans) query(now,l[k]);
if(dr<ans) query(now,r[k]);
}
else {
if(dr<ans) query(now,r[k]);
if(dl<ans) query(now,l[k]);
}
}
inline void del(int x) {
if(l[x]) del(l[x]);
st[++top]=x;p[++n]=id[x];
if(r[x]) del(r[x]);
}
inline int check(int k,int o) {
if(max(sz[l[k]],sz[r[k]])>sz[k]*alph) {
n=0,del(k);
return build(1,n,o);
}
return k;
}
int ins(int k,int now,int o) {
if(!k) {
k=newNode();
id[k]=p[now];pushup(k);
return k;
}
if(p[now].x[o]<=id[k].x[o]) l[k]=ins(l[k],now,o^1);
else r[k]=ins(r[k],now,o^1);
pushup(k);return check(k,o);
}
int main() {
n=read(),m=read();
for(re int i=1;i<=n;i++) p[i].x[0]=read(),p[i].x[1]=read();
build(1,n,0);int opt,x,y;
while(m--) {
opt=read(),x=read(),y=read();
if(opt==2) {
ans=inf;Point now;
now.x[0]=x,now.x[1]=y;
query(now,1);
printf("%d
",ans);
}
if(opt==1) {
p[++n].x[0]=x,p[n].x[1]=y;
ins(1,n,0);
}
}
return 0;
}