这天，SJY显得无聊。在家自己玩。在一个棋盘上，有N个黑色棋子。他每次要么放到棋盘上一个黑色棋子，要么放上一个白色棋子，如果是白色棋子，他会找出距离这个白色棋子最近的黑色棋子。此处的距离是 曼哈顿距离 即(|x1-x2|+|y1-y2|) 。现在给出N<=500000个初始棋子。和M<=500000个操作。对于每个白色棋子，输出距离这个白色棋子最近的黑色棋子的距离。同一个格子可能有多个棋子。

 

第一行两个数 N M

以后M行，每行3个数 t x y

如果t=1 那么放下一个黑色棋子

如果t=2 那么放下一个白色棋子

对于每个T=2 输出一个最小距离

 

 #include <bits/stdc++.h>

 inline int next(void) {

     int ret = , neg = , bit = getchar();

     while (bit < '') {

         if (bit == '-')

             neg ^= true;

         bit = getchar();

     }

     while (bit >= '') {

         ret = ret* + bit - '';

         bit = getchar();

     }

     return neg ? -ret : ret;

 }

 const int siz = 2e6 + ;

 const int inf = 2e9 + ;

 struct node {

     int pos[];

     int son[];

     int min[];

     int max[];

 }tree[siz];

 int root;

 int cmp_k;

 int qry_x;

 int qry_y;

 int answer;

 inline bool cmp(node a, node b) {

     return

         (a.pos[cmp_k] ^ b.pos[cmp_k])

     ?    (a.pos[cmp_k] < b.pos[cmp_k])

     :    (a.pos[!cmp_k] < b.pos[!cmp_k]);

 }

 inline void update(int t) {

     for (int i = ; i < ; ++i)if (tree[t].son[i])

         for (int j = ; j < ; ++j) {

             if (tree[t].min[j] > tree[tree[t].son[i]].min[j])

                 tree[t].min[j] = tree[tree[t].son[i]].min[j];

             if (tree[t].max[j] < tree[tree[t].son[i]].max[j])

                 tree[t].max[j] = tree[tree[t].son[i]].max[j];

         }

 }

 int build(int l, int r, int k) {

     int d = (l + r) >> ; cmp_k = k;

     std::nth_element(

         tree + l + ,

         tree + d + ,

         tree + r + ,

         cmp);

     if (l != d)tree[d].son[] = build(l, d - , !k);

     if (r != d)tree[d].son[] = build(d + , r, !k);

     tree[d].min[] = tree[d].max[] = tree[d].pos[];

     tree[d].min[] = tree[d].max[] = tree[d].pos[];

     return update(d), d;

 }

 inline void insert(int t) {

     for (int p = root, k = ; p != t; k = !k) {

         for (int i = ; i < ; ++i) {

             if (tree[p].min[i] > tree[t].min[i])

                 tree[p].min[i] = tree[t].min[i];

             if (tree[p].max[i] < tree[t].max[i])

                 tree[p].max[i] = tree[t].max[i];

         }

         int &to = tree[p].son[tree[t].pos[k] >= tree[p].pos[k]];

         to = to ? to : t; p = to;

     }

 }

 inline int dist(int t) {

     if (!t)return inf;

     int ret = ;

     if (qry_x < tree[t].min[])

         ret += tree[t].min[] - qry_x;

     if (qry_x > tree[t].max[])

         ret += qry_x - tree[t].max[];

     if (qry_y < tree[t].min[])

         ret += tree[t].min[] - qry_y;

     if (qry_y > tree[t].max[])

         ret += qry_y - tree[t].max[];

     return ret;

 }

 void query(int t) {

     answer = std::min(answer,

         std::abs(tree[t].pos[] - qry_x)

     +    std::abs(tree[t].pos[] - qry_y));

     if (dist(tree[t].son[]) < dist(tree[t].son[])) {

         if (dist(tree[t].son[]) < answer)query(tree[t].son[]);

         if (dist(tree[t].son[]) < answer)query(tree[t].son[]);

     } else {

         if (dist(tree[t].son[]) < answer)query(tree[t].son[]);

         if (dist(tree[t].son[]) < answer)query(tree[t].son[]);

     }

 }

 signed main(void) {

     int n = next();

     int m = next();

     for (int i = ; i <= n; ++i) {

         tree[i].pos[] = next();

         tree[i].pos[] = next();

     }

     root = build(, n, );

     for (int i = ; i <= m; ++i) {

         int k = next();

         int x = next();

         int y = next();

         if (k == ) {

             ++n;

             tree[n].min[] = tree[n].max[] = tree[n].pos[] = x;

             tree[n].min[] = tree[n].max[] = tree[n].pos[] = y;

             insert(n);

         }

         else {

             qry_x = x;

             qry_y = y;

             answer = inf;

             query(root);

             printf("%d\n", answer);

         }

     }

 }