这题想到CDQ分治其实挺好做的，就是一个三维偏序问题，唯一的问题是笔者一开始用CDQ套CDQ做这题，T了两个点，后来改成了CDQ+树状数组就过了（都开了O2优化），具体原理可能是树状数组操作可以转inline，相对快一些，而CDQ套CDQ的操作虽然复杂度也是$O(nlog^2n)$，但是是双指针操作，难以优化（蒟蒻瞎猜的，错了还请大佬轻喷）。以下附上CDQ套CDQ和CDQ+树状数组的两种实现方式和运行结果，供后人参考。（所以建议还是少用CDQ套CDQ，不然怎么T的都不知道）

CDQ套CDQ实现：

#include <bits/stdc++.h>
using namespace std;

const int maxn = 5e5 + 10;
const int INF = 1e8 + 10;
#define rep(i, x, y) for(int i =x; i <y; i++)

struct dool{
   int x, y, t, dis, type, dex;
}d[4][maxn], tmp[maxn], smp[maxn];
int res[maxn];
queue <int> q;

void InCDQ(int l, int r, dool *A)
{
   if(l==r) return;
   int mid = (l+r) >> 1, mx = -INF;
   InCDQ(l, mid, A), InCDQ(mid+1, r, A);
   for(int d1=l, d2=mid+1, i=l; i<=r; i++){
       if(d1 > mid || (d2 <= r && tmp[d1].y > tmp[d2].y)){
           if(tmp[d2].t == 1 && tmp[d2].type == 2 && mx != -INF){
               res[tmp[d2].dex] = min(res[tmp[d2].dex], tmp[d2].x+tmp[d2].y - mx);
           }
           smp[i] = tmp[d2++];
       }
       else{
           if(tmp[d1].t == 0 && tmp[d1].type == 1){
               mx = max(mx, tmp[d1].x + tmp[d1].y);
           }
           smp[i] = tmp[d1++];
       }
   }
   rep(i, l, r+1) tmp[i] = smp[i];
}

void CDQ(int l, int r, dool *A)
{
   if(l==r) return;
   int mid = (l+r) >> 1;
   CDQ(l, mid, A), CDQ(mid+1, r, A);
   for(int d1=l, d2=mid+1, i=l; i<=r; i++){
       if(d1 > mid || (d2 <= r && A[d1].x > A[d2].x)){
           tmp[i] = A[d2++];
           tmp[i].t = 1;
       }
       else{
           tmp[i] = A[d1++];
           tmp[i].t = 0;
       }
   }
   rep(i, l, r+1) A[i] = tmp[i];
   InCDQ(l, r, A);
}

int main()
{
   ios::sync_with_stdio(false);
   int n, m;
   cin >> n >> m;
   rep(i, 0, n){
       cin >> d[0][i].x >> d[0][i].y;
       d[0][i].type = 1, d[0][i].t = 0;
       d[1][i] = d[0][i], d[2][i] = d[0][i], d[3][i] = d[0][i];
       d[1][i].x = -d[0][i].x;
       d[2][i].y = -d[0][i].y;
       d[3][i].x = -d[0][i].x, d[3][i].y = -d[0][i].y;
   }
   rep(i, n, m+n){
       cin >> d[0][i].type >> d[0][i].x >> d[0][i].y;
       d[0][i].t = i-n+1, d[0][i].dex = i-n+1;
       d[1][i] = d[0][i], d[2][i] = d[0][i], d[3][i] = d[0][i];
       d[1][i].x = -d[0][i].x;
       d[2][i].y = -d[0][i].y;
       d[3][i].x = -d[0][i].x, d[3][i].y = -d[0][i].y;
       if(d[0][i].type == 2) q.push(i-n+1);
   }

   memset(res, INF, sizeof(res));
   rep(i, 0, 4) CDQ(0, m+n, d[i]);
   while(!q.empty()){
       cout << res[q.front()];
       q.pop();
       if(!q.empty()) cout << '\n';
   }
}

CDQ套CDQ评测结果： CDQ+树状数组实现：

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e6 + 10;
const int INF = 1e8 + 10;
const int BOUND = 1e6 + 1;
#define rep(i, x, y) for(int i =x; i <y; i++)
#define lowbit(x) x&(-x)

struct dool{
    int x, y, t, dis, type, dex;
}d[4][maxn], tmp[maxn];
int res[maxn], T[maxn], n, m;
queue <int> q;

inline void insert(int d, int val)
{
    for(int i = d; i <= maxn; i += lowbit(i)) T[i] = max(T[i], val);
}
inline int query(int d)
{
    int ans = 0;
    for(int i = d; i > 0; i -= lowbit(i)) ans = max(T[i], ans);
    return ans;
}
inline void erase(int d)
{
    for(int i = d; i <= maxn; i += lowbit(i)) T[i] = 0;
}

void CDQ(int l, int r, dool *A)
{
    if(l==r) return;
    int mid = (l+r) >> 1;
    CDQ(l, mid, A), CDQ(mid+1, r, A);
    for(int d1=l, d2=mid+1, i=l; i<=r; i++){
        if(d1 > mid || (d2 <= r && A[d1].x > A[d2].x)){
            tmp[i] = A[d2++];
            if(tmp[i].type == 2){
                int mx = query(tmp[i].y);
                if(mx) res[tmp[i].dex] = min(tmp[i].x + tmp[i].y - mx, res[tmp[i].dex]);
            }
        }
        else{
            tmp[i] = A[d1++];
            if(tmp[i].type == 1) insert(tmp[i].y, tmp[i].x+tmp[i].y);
        }
    }
    rep(i, l, r+1){
        A[i] = tmp[i];
        if(tmp[i].type == 1) erase(tmp[i].y);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    memset(T, 0, sizeof(T));
    memset(res, INF, sizeof(res));

    cin >> n >> m;
    rep(i, 0, n){
        cin >> d[0][i].x >> d[0][i].y;
        d[0][i].y++;
        d[0][i].type = 1, d[0][i].t = 0;
        d[1][i] = d[0][i], d[2][i] = d[0][i], d[3][i] = d[0][i];
        d[1][i].x = BOUND-d[0][i].x;
        d[2][i].y = BOUND-d[0][i].y;
        d[3][i].x = BOUND-d[0][i].x, d[3][i].y = BOUND-d[0][i].y;
    }
    rep(i, n, m+n){
        cin >> d[0][i].type >> d[0][i].x >> d[0][i].y;
        d[0][i].y++;
        d[0][i].t = i-n+1, d[0][i].dex = i-n+1;
        d[1][i] = d[0][i], d[2][i] = d[0][i], d[3][i] = d[0][i];
        d[1][i].x = BOUND-d[0][i].x;
        d[2][i].y = BOUND-d[0][i].y;
        d[3][i].x = BOUND-d[0][i].x, d[3][i].y = BOUND-d[0][i].y;
        if(d[0][i].type == 2) q.push(i-n+1);
    }

    rep(i, 0, 4) CDQ(0, m+n, d[i]);
    while(!q.empty()){
        cout << res[q.front()];
        q.pop();
        if(!q.empty()) cout << '\n';
    }
}

CDQ+树状数组评测结果：