题目背景
感谢@浮尘ii 提供的一组hack数据
题目描述
Ayu 在七年前曾经收到过一个天使玩偶，当时她把它当作时间囊埋在了地下。而七年后 的今天，Ayu 却忘了她把天使玩偶埋在了哪里，所以她决定仅凭一点模糊的记忆来寻找它。
我们把 Ayu 生活的小镇看作一个二维平面坐标系，而 Ayu 会不定时地记起可能在某个点 (xmy) 埋下了天使玩偶；或者 Ayu 会询问你，假如她在 (x,y) ，那么她离近的天使玩偶可能埋下的地方有多远。
因为 Ayu 只会沿着平行坐标轴的方向来行动，所以在这个问题里我们定义两个点之间的距离为dist(A,B)=|Ax-Bx|+|Ay-By|。其中 Ax 表示点 A的横坐标，其余类似。
输入输出格式
输入格式：
第一行包含两个整数n和m ，在刚开始时，Ayu 已经知道有n个点可能埋着天使玩偶， 接下来 Ayu 要进行m 次操作
接下来n行，每行两个非负整数 (xi,yi)，表示初始n个点的坐标。
再接下来m 行，每行三个非负整数 t,xi,yi。
如果t=1 ，则表示 Ayu 又回忆起了一个可能埋着玩偶的点 (xi,yi) 。
如果t=2 ，则表示 Ayu 询问如果她在点 (xi,yi) ，那么在已经回忆出来的点里，离她近的那个点有多远
输出格式：
对于每个t=2 的询问，在单独的一行内输出该询问的结果。
输入输出样例
2 3
1 1
2 3
2 1 2
1 3 3
2 4 2
1
2
说明
n,m<=300 000
xi,yi<=1 000 000
Solution：
本题巨说是点分治裸题。。。然而我用$kd-tree$水了波$90$。（应该是可以$A$的，但是暂时不会玄学转树，留坑待填～）
有必要先解释一下变量含义：$(d[0],d[1])$为当前根节点的坐标，$(mn[0],mn[1])$表示当前节点代表的二维平面中最左下角的坐标，$(mx[0],mx[1])$表示最右上角的坐标，$l,r$分别表示当前节点的左、右儿子。
思路比较简单，构建二维搜索树，将每个点拍到面上去，从根节点往下每层交替按$x$和$y$为关键字建树。
建树过程，要尽可能使得树保持平衡，所以每次以区间中间为当前根节点建树，二维平面分为左部和右部两部分，分别表示当前节点的左儿子和右儿子。
代码：
#include<bits/stdc++.h>
#define il inline
#define For(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define Min(a,b) ((a)>(b)?(b):(a))
#define Max(a,b) ((a)>(b)?(a):(b))
using namespace std;
const int N=,inf=;
int n,m,x,y,opt,ans,cmpd,root;
struct node{
int d[],l,r,mn[],mx[];
bool operator <(const node a){
return ((d[cmpd]<a.d[cmpd])||(d[cmpd]==a.d[cmpd]&&d[!cmpd]<a.d[!cmpd]));
}
}t[N]; il int gi(){
int a=;char x=getchar();bool f=;
while((x<''||x>'')&&x!='-')x=getchar();
if(x=='-')x=getchar(),f=;
while(x>=''&&x<='')a=(a<<)+(a<<)+x-,x=getchar();
return f?-a:a;
} il void update(int rt){
int ls=t[rt].l,rs=t[rt].r;
if(ls){
t[rt].mn[]=Min(t[rt].mn[],t[ls].mn[]);
t[rt].mn[]=Min(t[rt].mn[],t[ls].mn[]);
t[rt].mx[]=Max(t[rt].mx[],t[ls].mx[]);
t[rt].mx[]=Max(t[rt].mx[],t[ls].mx[]);
}
if(rs){
t[rt].mn[]=Min(t[rt].mn[],t[rs].mn[]);
t[rt].mn[]=Min(t[rt].mn[],t[rs].mn[]);
t[rt].mx[]=Max(t[rt].mx[],t[rs].mx[]);
t[rt].mx[]=Max(t[rt].mx[],t[rs].mx[]);
}
} il int build(int l,int r,int tw){
cmpd=tw;
int mid=l+r>>;
nth_element(t+l+,t+mid+,t+r+);
t[mid].mn[]=t[mid].mx[]=t[mid].d[];
t[mid].mn[]=t[mid].mx[]=t[mid].d[];
if(l!=mid)t[mid].l=build(l,mid-,!tw);
if(r!=mid)t[mid].r=build(mid+,r,!tw);
update(mid);
return mid;
} il void insert(int rt){
int op=,p=root;
while(){
if(t[rt].mn[]<t[p].mn[])t[p].mn[]=t[rt].mn[];
if(t[rt].mn[]<t[p].mn[])t[p].mn[]=t[rt].mn[];
if(t[rt].mx[]>t[p].mx[])t[p].mx[]=t[rt].mx[];
if(t[rt].mx[]>t[p].mx[])t[p].mx[]=t[rt].mx[];
if(t[rt].d[op]>=t[p].d[op]){
if(!t[p].r){t[p].r=rt;return;}
else p=t[p].r;
}
else {
if(!t[p].l){t[p].l=rt;return;}
else p=t[p].l;
}
op=!op;
}
} il int mhd(int rt,int x,int y){
int s=;
if(x<t[rt].mn[])s+=(t[rt].mn[]-x);
if(x>t[rt].mx[])s+=(x-t[rt].mx[]);
if(y<t[rt].mn[])s+=(t[rt].mn[]-y);
if(y>t[rt].mx[])s+=(y-t[rt].mx[]);
return s;
} il void query(int rt){
int d0,dl,dr;
d0=abs(t[rt].d[]-x)+abs(t[rt].d[]-y);
if(d0<ans)ans=d0;
if(t[rt].l)dl=mhd(t[rt].l,x,y);
else dl=inf;
if(t[rt].r)dr=mhd(t[rt].r,x,y);
else dr=inf;
if(dl<dr){
if(dl<ans)query(t[rt].l);
if(dr<ans)query(t[rt].r);
}
else {
if(dr<ans)query(t[rt].r);
if(dl<ans)query(t[rt].l);
}
} int main(){
n=gi(),m=gi();
For(i,,n) t[i].d[]=gi(),t[i].d[]=gi();
root=build(,n,);
while(m--){
opt=gi(),x=gi(),y=gi();
if(opt==){
n++;
t[n].mn[]=t[n].mx[]=t[n].d[]=x;
t[n].mn[]=t[n].mx[]=t[n].d[]=y;
insert(n);
}
else {
ans=inf;
query(root);
printf("%d\n",ans);
}
}
return ;
}