/**************************************************************

     Problem: 2716

     User: Tunix

     Language: C++

     Result: Accepted

     Time:16492 ms

     Memory:26280 kb

 ****************************************************************/

 //BZOJ 2716

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<iostream>

 #include<algorithm>

 #define rep(i,n) for(int i=0;i<n;++i)

 #define F(i,j,n) for(int i=j;i<=n;++i)

 #define D(i,j,n) for(int i=j;i>=n;--i)

 #define pb push_back

 using namespace std;

 typedef long long LL;

 inline int getint(){

     int r=,v=; char ch=getchar();

     for(;!isdigit(ch);ch=getchar()) if (ch=='-') r=-;

     for(; isdigit(ch);ch=getchar()) v=v*-''+ch;

     return r*v;

 }

 const int N=,INF=1e9;

 /*******************template********************/

 struct node{

     int d[],mn[],mx[],l,r;

     int& operator [] (int x){return d[x];}

     void read(){d[]=getint(); d[]=getint();}

 }t[N],tmp;

 int n,m,D,root,ans,cnt;

 inline int dis(node a,node b){return abs(a[]-b[])+abs(a[]-b[]);}

 bool operator < (node a,node b){return a[D]<b[D] || (a[D]==b[D] && a[!D]<b[!D]);}

 #define L t[o].l

 #define R t[o].r

 #define mid (l+r>>1)

 void Push_up(int o){

     F(i,,){

         if (L){ t[o].mn[i]=min(t[o].mn[i],t[L].mn[i]); t[o].mx[i]=max(t[o].mx[i],t[L].mx[i]);}

         if (R){ t[o].mn[i]=min(t[o].mn[i],t[R].mn[i]); t[o].mx[i]=max(t[o].mx[i],t[R].mx[i]);}

     }

 }

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

     D=dir;

     nth_element(t+l,t+mid,t+r+);

     F(i,,) t[mid].mn[i]=t[mid].mx[i]=t[mid][i];

     if (l<mid) t[mid].l=build(l,mid-,dir^);

     if (r>mid) t[mid].r=build(mid+,r,dir^);

     Push_up(mid);

     return mid;

 }

 inline void Insert(int &o,int dir){

     if (!o){

         o=++cnt; t[o]=tmp;

         F(i,,) t[o].mn[i]=t[o].mx[i]=t[o][i];

         return;

     }

     if (tmp[dir]<t[o][dir]) Insert(L,dir^);

     else Insert(R,dir^);

     Push_up(o);

 }

 inline int getdis(int o){

     if (!o) return INF;

     int ans=;

     F(i,,) ans+=max(,t[o].mn[i]-tmp[i]);

     F(i,,) ans+=max(,tmp[i]-t[o].mx[i]);

     return ans;

 }

 inline void query(int o){

     int dl=getdis(L),dr=getdis(R),d0=dis(t[o],tmp);

     ans=min(ans,d0);

     if (dl<dr){

         if (dl<ans) query(L);

         if (dr<ans) query(R);

     }else{

         if (dr<ans) query(R);

         if (dl<ans) query(L);

     }

 }

 int main(){

 #ifndef ONLINE_JUDGE

     freopen("2716.in","r",stdin);

     freopen("2716.out","w",stdout);

 #endif

     cnt=n=getint(); m=getint();

     F(i,,n) t[i].read();

     root=build(,n,);

     F(i,,m){

         int t=getint(); tmp.read();

         if (t==) Insert(root,);

         else{

             ans=INF;

             query(root);

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

         }

     }

     return ;

 }

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

 

第一行两个数 N M

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

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

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

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