【题意】
Ayu在七年前曾经收到过一个天使玩偶，当时她把它当做时间囊埋在了地下。
而七年后的今天，Ayu却忘了她把天使玩偶埋在了哪里，所以她决定仅凭一点模糊的记忆来寻找它。
我们把Ayu生活的小镇看做一个二维平面直角坐标系，而Ayu会不定时的记起可能在某个点(x,y)埋下了天使玩偶。
或者Ayu会询问你，假如她在(x,y)，那么她离最近的天使玩偶可能埋下的地方有多远。
因为Ayu只会沿着平行坐标轴的方向来行动，所以在这个问题里我们定义两个点之间的距离为曼哈顿距离：
dist(A,B)=|Ax−Bx|+|Ay−By|
dist(A,B)=|Ax−Bx|+|Ay−By|
其中Ax，Ay表示点A的横坐标，其余类似。
前言：
分治是一种有趣的方法。
分析：
为了去掉绝对值符号，不妨把询问分成4种，分别询问左下、左上、右下、右上方向上最近的点的距离，4个答案的最小值即为答案。
设为询问点的坐标，为前面天使玩偶的坐标。 情况如下图：
可以发现上面的符号是一样的。
我们需要用CDQ分治求解。
主要思想就是：把前面的天使玩偶更新后面的询问。用树状数组维护前缀最大值。
需要注意的是：
- 是的，我们其实只用把修改的位置重置即可。
- 对于左上、右上的情况，树状数组更新的是
代码：
#pragma GCC optimze("Ofast")
#pragma GCC optimze(2)
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#define g getchar()
using namespace std;
const int N=1e6+10;
struct rec { int x,y,z; }a[N],b[N]; //原操作序列
bool operator <(rec a,rec b) {
return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
int t,n,m;
int ans[N],c[N],tot;//BIT
int ask(int x) {
int y=c[0];
for( ;x;x&=x-1) y=max(y,c[x]);
return y;
}
void up(int x,int y) {//树状数组维护前缀最大值
for( ;x<tot&&c[x]<y;x+=x&-x)
c[x]=y;
}
int sta[N],top;//装上传的标号
void calc(int st,int ed,int d,int dx,int dy) {
for(int i=st;i!=ed;i+=d) {
int y=(dy==1)?b[i].y:tot-b[i].y;
int tmp=b[i].x*dx+b[i].y*dy;
if(a[b[i].z].z==1) up(y,tmp),sta[++top]=b[i].z;
else ans[b[i].z]=min(ans[b[i].z],tmp-ask(y));
}
while(top) //重置树状数组(避免memset)
for(int x=(dy==1)?a[sta[top--]].y:tot-a[sta[top--]].y;x<tot&&c[x]>c[0];x+=x&-x)
c[x]=c[0];
}
void cdq(int l,int r) {
if(l==r||r<=n)return ;
int mid=(l+r)>>1;
cdq(l,mid);
cdq(mid+1,r);
t=0;
for(int i=l;i<=r;i++)
if( (i<=mid) ^ (a[i].z==2) )
b[++t]=a[i],b[t].z=i;
sort(b+1,b+t+1);
calc(1,t+1,1,1,1); calc(t,0,-1,-1,-1);
calc(1,t+1,1,1,-1); calc(t,0,-1,-1,1);
}
void qr(int &x) {
char c=g;x=0;
while(!isdigit(c))c=g;
while(isdigit(c))x=x*10+c-'0',c=g;
}
void write(int x) {
if(x/10)write(x/10);
putchar(x%10+'0');
}
void pri(int x) { write(x) ; puts("") ;}
int main() {
qr(n);qr(m);m+=n;
for(int i=1;i<=n;i++)
qr(a[i].x),qr(a[i].y),a[i].y++,a[i].z=1;
for(int i=n+1;i<=m;i++)
qr(a[i].z),qr(a[i].x),qr(a[i].y),a[i].y++;
for(int i=1;i<=m;i++)tot=max(tot,a[i].y);
tot++;
memset(c,-63,(tot+1)<<2);
memset(ans,63,(m+1)<<2);
cdq(1,m);
for(int i=n+1;i<=m;i++)
if(a[i].z==2) pri(ans[i]);
return 0;
}