2648: SJY摆棋子

题目连接：

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

Hint

题意

题解：

kdtree裸题

代码

#include
    
     using namespace std;const int maxn = 1000005;#define INF 1000000000struct arr{    int d[2],min[2],max[2],l,r;};int D,root,x,y,ans,n,m,tot,op;;inline int cmp(arr a,arr b){    return a.d[D]
     
      
       >1;    nth_element(a+l+1,a+mid+1,a+r+1,cmp);    a[mid].min[0]=a[mid].max[0]=a[mid].d[0];    a[mid].min[1]=a[mid].max[1]=a[mid].d[1];    if (l!=mid) a[mid].l=build(l,mid-1,dd^1);    if (mid!=r) a[mid].r=build(mid+1,r,dd^1);    if (a[mid].l) up(mid,a[mid].l);    if (a[mid].r) up(mid,a[mid].r);    return mid;}void insert(int k){    int p=root;D=0;    while (1)    {        up(p,k);        if (a[k].d[D]<=a[p].d[D]){if (!a[p].l) {a[p].l=k;return;} p=a[p].l;}        else {if (!a[p].r) {a[p].r=k;return;} p=a[p].r;}        D^=1;    }}int getdis(int k){    int res=0;    if (x
       
        a[k].max[0]) res+=x-a[k].max[0];    if (y
        
         a[k].max[1]) res+=y-a[k].max[1];    return res;}void ask(int k){  int d0=abs(a[k].d[0]-x)+abs(a[k].d[1]-y);  if (d0