CDQ分治其实就是一个离线分治算法。
对于每一个询问，只需考虑原有的点，以及在其之前的修改操作对其造成的影响。
简单来讲，对于第$k$项询问，只需统计$1\sim k-1$的修改操作(把原有点也看作修改)就行了。
如果每一次都仅对一个询问进行统计答案，过于浪费，因此可以整体分治询问统计答案。
具体分治过程是这样的:

  1. 设$mid=l+r>>1$,递归计算$solve(l,mid),solve(mid+1,r)$
  2. 计算第$l\sim mid$项操作中的所有“修改”对第$mid+1\sim r$操作中所有“查询”造成的影响。
    正确性证明:

对于第$k$项询问，若$k\le mid$，那么$solve(l,mid)$就已经解决了第$l,k-1$项操作中的“修改”对它的影响。
若$k>mid$,那么$solve(l,r)$解决第$l,mid$项修改,$solve(mid+1,r)$解决$mid+1,r$，证毕。

其实这道题是一道三维偏序问题。
简要题意就是，统计对于$\forall i$，询问$a_j<=a_i,b_j<=b_i,c_j<=c_i$的$j$的个数。
转化为本题题意:

  • 第一维即为时间，第二维即为$x$坐标，第三维即为$y$坐标
    通常来讲，第一维需要整体排序，第二维需要在分治时，分$l,mid$,$mid+1,r$两端排序，第三维通过数据结构维护。

对于本题来讲，以左下为例:
对于第$k$个询问询问$x,y,z$,统计前$k-1$项的修改操作对其答案的贡献，$ans=\min (x+y)-(x_i+y_i)$。
左上，右下，右上可自行推导。

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#define gc getchar()
using namespace std;
const int N=5e5+10;
const int inf=0xcfcfcfcf;
inline void qr(int &x)
{
    char c=gc;int f=1;x=0;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(int x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int n,m,t,tot;
struct node{int x,y,z;bool operator <(const node a)const{return x==a.x?y<a.y:x<a.x;}}a[N<<1],b[N<<1];
int c[N<<1],ans[N<<1],mx;
int ask(int x){int ans=inf;for(;x;x-=x&-x)ans=max(ans,c[x]);return ans;}
void add(int x,int k){for(;x<mx;x+=x&-x)c[x]=max(c[x],k);}
void calc(int l,int r,int d,int dx,int dy)
{
    for(int i=l;i!=r;i+=d)
    {
        int y=(dy==1?b[i].y:mx-b[i].y);
        //mx-b[i].y是b[i].y水平平移的结果，因为树状数组只能统计1~b[i].y，若统计上方的点时，得处理成-b[i].y，才能统计上方的点，为了保证正数，因此水平平移。 
        int temp=b[i].x*dx+b[i].y*dy;
        if(a[b[i].z].z==1)add(y,temp);
        else ans[b[i].z]=min(ans[b[i].z],abs(temp-ask(y)));
    }
    for(int i=l;i!=r;i+=d)//还原 
        if(a[b[i].z].z==1)
        {
            int y=(dy==1?b[i].y:mx-b[i].y);
            for(;y<mx;y+=y&-y)c[y]=inf;
        }
}
void cdqdiv(int l,int r)
{
    int mid=l+r>>1;
    if(l<mid)cdqdiv(l,mid);
    if(r>mid+1)cdqdiv(mid+1,r);
    int len=0;
    for(int i=l;i<=r;i++)
        if((i<=mid&&a[i].z==1)||(i>mid&&a[i].z==2))
            b[++len]=a[i],b[len].z=i;//处理第一维时间 
    sort(b+1,b+len+1);//处理第二维x 
    calc(1,len+1,1,1,1),calc(1,len+1,1,1,-1);//处理第三维y 
    calc(len,0,-1,-1,1),calc(len,0,-1,-1,-1);
}
int main()
{
    int n,m;qr(n),qr(m);memset(c,0xcf,sizeof(c));mx=inf;memset(ans,0x3f,sizeof(ans));
    for(int i=1;i<=n;i++)qr(a[i].x),qr(a[i].y),a[i].z=1,++a[i].y;
    for(int i=n+1;i<=n+m;i++)qr(a[i].z),qr(a[i].x),qr(a[i].y),++a[i].y;
    for(int i=1;i<=n+m;i++)mx=max(mx,a[i].y);++mx;
    cdqdiv(1,n+m);
    for(int i=n+1;i<=n+m;i++)if(a[i].z==2)qw(ans[i]),puts("");
    return 0;
}