Description
这天，SJY显得无聊。在家自己玩。在一个棋盘上，有N个黑色棋子。他每次要么放到棋盘上一个黑色棋子，要么放上一个白色棋子，如果是白色棋子，他会找出距离这个白色棋子最近的黑色棋子。此处的距离是 曼哈顿距离 即(|x1-x2|+|y1-y2|) 。现在给出N<=500000个初始棋子。和M<=500000个操作。对于每个白色棋子，输出距离这个白色棋子最近的黑色棋子的距离。同一个格子可能有多个棋子。
Input
第一行两个数 N M
以后M行，每行3个数 t x y
如果t=1 那么放下一个黑色棋子
如果t=2 那么放下一个白色棋子
Output
对于每个T=2 输出一个最小距离
Sample Input
2 3
1 1
2 3
2 1 2
1 3 3
2 4 2
Sample Output
1
2
分析：
KD tree
http://blog.csdn.net/silangquan/article/details/41483689
讲得超好，而且配图精良
http://blog.sina.com.cn/s/blog_8d5d2f040101888r.html
这个博主的代码超级优美（好像是一个叫RZZ的大佬，鸣谢）
题目的输入就把我看蒙了，
（不是说好只有M+1行的吗）
后来看了题目才知道
棋盘上初始有n黑色个棋子
kdtree的原理想必都明白吧
（看看那些大佬的blog就好了，这里不再废话）
大佬们讲的大多都是理论上的东西，
很少讲代码实现，所以这篇博文就来剖析一下kdtree的代码
每个kdtree节点维护的信息：
(d[0],d[1]) 该节点代表的子树的根节点
(l,r) 该节点的左右儿子
(mx[0],mx[1]) 该节点代表的子树管理的区间右上角
(mn[0],mn[1]) 该节点代表的子树管理的区间左下角
kdtree的构建和插入是不一样的
(可能有人会说，肯定不一样啊干，
但是有些数据结构的初始化就直接处理成了插入)
一 . kd的构建
构建的主体思想就是不断地寻找区间中点，
把区间划分成尽量均等的两份，不断地递归构建下去
为了让区间划分平衡，区间的划分方向是’临代不同，隔代遗传’的，如图
代码中，我们先利用nth_element函数找到该区间中间的节点，并把ta放到树的中间
nth_element函数
求一个容器中第n（大/小）的元素
函数参数：nth_element(first,nth,last,compare);
注意：nth_element函数会将第n（大/小）的元素放到第n的位置，
且比第n（大/小）的元素会放到（右边/左边）
之后递归构造左右区间，不要忘了把切割方向转变一下
这个D/cmpd就是当前的分割方向
在build函数内部，我们并没有维护每个节点代表的区间
这些任务都是在update里完成的
不要忘了build返回值是int，我们要靠build找到这棵树的根
二 . update和cmp
cmp
我们按照当前的cmpd（切割方向比较平面上的点）
update
在这个函数中我们进行了kdtree节点代表区间的维护
当前节点是ta的左儿子和右儿子所代表的区间取max
（担心有人不懂，来看一下图）
三 . kdtree的节点插入
insert
这就有点像主席树的插入
一个元素的插入会引起ta到根的路径上所有节点的变化
首先引起的就是管辖区间的变化
如果插入的节点在当前整棵kdtree管辖的区间之外
那就要重新维护mn和mx了
之后就是比较插入点和当前节点在D(规定切割方向上的大小了)
然后进行插入
注意，在该坐标相等的情况下归入右节点
四 . kdtree的查询
我觉得这一部分较困难
函数中有三个变量 d0,dl,dr
d0表示当前点到查询点的距离
dl表示当前点左儿子到查询点的距离
dr表示当前点右儿子到查询点的距离
如果dl或dr < ans(当前答案)
那最终的答案就有可能在ta们分管的区间内，
我们就要进行这个方向上的查找
如果dl和dr都小于ans
那我们优先dl，dr中较小的一个进行查找
这个函数中还包含一个小函数，就是求曼哈顿距离的
这里写代码片
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int INF=0x33333333;
struct node{
int d[2],l,r,mn[2],mx[2];
};
node t[800001];
int n,m,x,y,opt,ans,cmpd,root;
int cmp(const node &a,const node &b)
{
return ((a.d[cmpd]<b.d[cmpd])||((a.d[cmpd]==b.d[cmpd])&&(a.d[!cmpd]<b.d[!cmpd])));
}
void update(int bh)
{
int lc=t[bh].l;
int rc=t[bh].r;
if (lc)
{
t[bh].mn[0]=min(t[bh].mn[0],t[lc].mn[0]);
t[bh].mn[1]=min(t[bh].mn[1],t[lc].mn[1]);
t[bh].mx[0]=max(t[bh].mx[0],t[lc].mx[0]);
t[bh].mx[1]=max(t[bh].mx[1],t[lc].mx[1]);
}
if (rc)
{
t[bh].mn[0]=min(t[bh].mn[0],t[rc].mn[0]);
t[bh].mn[1]=min(t[bh].mn[1],t[rc].mn[1]);
t[bh].mx[0]=max(t[bh].mx[0],t[rc].mx[0]);
t[bh].mx[1]=max(t[bh].mx[1],t[rc].mx[1]);
}
}
int build(int l,int r,int D)
{
cmpd=D;
int mid=(l+r)>>1;
nth_element(t+l+1,t+mid+1,t+r+1,cmp);
t[mid].mn[0]=t[mid].mx[0]=t[mid].d[0];
t[mid].mn[1]=t[mid].mx[1]=t[mid].d[1];
if (l!=mid) t[mid].l=build(l,mid-1,!D);
if (r!=mid) t[mid].r=build(mid+1,r,!D);
update(mid);
return mid;
}
void insert(int now)
{
int D,p;
D=0; p=root;
while (1)
{
if (t[now].mn[0]<t[p].mn[0]) t[p].mn[0]=t[now].mn[0];
if (t[now].mx[0]>t[p].mx[0]) t[p].mx[0]=t[now].mx[0];
if (t[now].mn[1]<t[p].mn[1]) t[p].mn[1]=t[now].mn[1];
if (t[now].mx[1]>t[p].mx[1]) t[p].mx[1]=t[now].mx[1];
if (t[now].d[D]>=t[p].d[D])
{
if (t[p].r==0)
{
t[p].r=now;
return;
}
else p=t[p].r;
}
else
{
if (t[p].l==0)
{
t[p].l=now;
return;
}
else p=t[p].l;
}
D=!D;
}
}
int dis(int p,int x,int y)
{
int d=0;
if (x<t[p].mn[0]) d+=(t[p].mn[0]-x);
if (x>t[p].mx[0]) d+=(x-t[p].mx[0]);
if (y<t[p].mn[1]) d+=(t[p].mn[1]-y);
if (y>t[p].mx[1]) d+=(y-t[p].mx[1]);
return d;
}
void ask(int now)
{
int d0,dl,dr;
d0=abs(t[now].d[0]-x)+abs(t[now].d[1]-y);
if (d0<ans) ans=d0;
if (t[now].l) dl=dis(t[now].l,x,y);
else dl=INF;
if (t[now].r) dr=dis(t[now].r,x,y);
else dr=INF;
if (dl<dr)
{
if (dl<ans) ask(t[now].l);
if (dr<ans) ask(t[now].r);
}
else
{
if (dr<ans) ask(t[now].r);
if (dl<ans) ask(t[now].l);
}
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
scanf("%d%d",&t[i].d[0],&t[i].d[1]);
root=build(1,n,0);
for (int i=1;i<=m;i++)
{
scanf("%d%d%d",&opt,&x,&y);
if (opt==1)
{
n++;
t[n].mn[0]=t[n].mx[0]=t[n].d[0]=x;
t[n].mn[1]=t[n].mx[1]=t[n].d[1]=y;
insert(n);
}
else
{
ans=INF;
ask(root);
printf("%d
",ans);
}
}
}