题目大意：
这明明是一道KD-Tree，CDQ分治是TLE的做法
化简式子，$|x1-x2|-|y1-y2|=(x1+y1)-(x2+y2)$
而$CDQ$分治只能解决$x1 \leq x2,y1 \leq y2$的情况
把每次插入操作都相当于一个三元组$<x,y,t>$，权值是$x+y$。这就是一个三维偏序问题，用树状数组维护最大值即可
所以通过坐标变换，跑$4$次$CDQ$就行了？
没错，你会像我一样T得飞起
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N1 1001000
#define M1 1001000
#define ll long long
#define dd double
#define inf 233333333
using namespace std; int gint()
{
int ret=,fh=;char c=getchar();
while(c<''||c>''){if(c=='-')fh=-;c=getchar();}
while(c>=''&&c<=''){ret=ret*+c-'';c=getchar();}
return ret*fh;
}
int n,m,ma,nm,mx,my;
struct BIT{
int ma[M1];
void update(int x,int w){ for(int i=x;i<=my;i+=(i&(-i))) ma[i]=max(ma[i],w); }
int query(int x){ int ans=-inf; for(int i=x;i;i-=(i&(-i))) ans=max(ans,ma[i]); return ans; }
void clr(int x){ for(int i=x;i<=my;i+=(i&(-i))) ma[i]=-inf;}
void init(){ for(int i=;i<=my;i++) ma[i]=-inf; }
}s;
struct node{int x,y,p,t,ans;}a[N1],tmp[N1];
int cmp1(node s1,node s2){ if(s1.x!=s2.x) return s1.x<s2.x; if(s1.y!=s2.y) return s1.y<s2.y; return s1.p<s2.p;}
int cmpt(node s1,node s2){ return s1.t<s2.t; }
int que[N1],tl; void CDQ(int L,int R)
{
if(R-L<=) return;
int i,j,k,M=(L+R)>>;
for(i=L,j=M,k=L;k<R;k++)
{
if(a[k].t<M) tmp[i++]=a[k];
else tmp[j++]=a[k];
}
for(k=L;k<R;k++) a[k]=tmp[k];
CDQ(L,M);
for(i=L,j=M;i<M&&j<R;)
{
if(cmp1(a[i],a[j])){ if(a[i].p==) { s.update(a[i].y,a[i].x+a[i].y); que[++tl]=i; } i++; }
else{ if(a[j].p==) a[j].ans=min(a[j].ans,(a[j].x+a[j].y)-s.query(a[j].y)); j++; }
}
while(j<R){ if(a[j].p==) a[j].ans=min(a[j].ans,(a[j].x+a[j].y)-s.query(a[j].y)); j++; }
while(tl){ s.clr(a[que[tl--]].y); }
CDQ(M,R);
for(i=L,j=M,k=;i<M&&j<R;)
{
if(cmp1(a[i],a[j])) tmp[++k]=a[i++];
else tmp[++k]=a[j++];
}
while(i<M){ tmp[++k]=a[i++]; }
while(j<R){ tmp[++k]=a[j++]; }
for(k=L;k<R;k++) a[k]=tmp[k-L+];
}
int p[N1]; int main()
{
int i,j; n=gint(); m=gint(); nm=n+m;
for(i=;i<=n;i++){ a[i].p=; a[i].x=gint()+; a[i].y=gint()+; a[i].t=i; a[i].ans=inf; mx=max(mx,a[i].x); my=max(my,a[i].y); }
for(i=n+;i<=n+m;i++){ a[i].p=gint(); a[i].x=gint()+; a[i].y=gint()+; a[i].t=i; a[i].ans=inf; mx=max(mx,a[i].x); my=max(my,a[i].y); }
sort(a+,a+nm+,cmp1); s.init();
CDQ(,nm+);
for(i=;i<=nm;i++){ a[i].x=mx-a[i].x+; } sort(a+,a+nm+,cmp1);
CDQ(,nm+);
for(i=;i<=nm;i++){ a[i].y=my-a[i].y+; } sort(a+,a+nm+,cmp1);
CDQ(,nm+);
for(i=;i<=nm;i++){ a[i].x=mx-a[i].x+; } sort(a+,a+nm+,cmp1);
CDQ(,nm+);
sort(a+,a+nm+,cmpt);
for(i=n+;i<=nm;i++) if(a[i].p==) printf("%d\n",a[i].ans);
return ;
}