CDQ分治模版，马蜂抽象，玄关见谅。

题目

code；

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e6+10;
int n,m,q,t[N],ans[N];
void add(int x,int val){for(;x<N;x+=x&-x)t[x]=max(t[x],val);}
int query(int x){int res=-1;for(;x;x-=x&-x)res=max(res,t[x]);return res;}
void clear(int x){for(;x<N;x+=x&-x)t[x]=-1;}
struct node{
    int op,x,y;
}a[N],b[N];
void solve(int l,int r)
{
    if(l==r)return;
    int mid=(l+r)>>1,cnt=0;
    solve(l,mid);
    solve(mid+1,r);
    for(int i=l;i<=mid;i++)
        if(!a[i].op)b[++cnt]=a[i];
    for(int i=mid+1;i<=r;i++)
        if(a[i].op)b[++cnt]=a[i];
    sort(b+1,b+1+cnt,[&](node x,node y){return x.x<y.x;});
    for(int i=1;i<=cnt;i++)
    {
        if(!b[i].op)add(b[i].y,b[i].x+b[i].y);
        else{
            int get=query(b[i].y);
            if(get==-1)continue;
            else ans[b[i].op]=min(ans[b[i].op],b[i].x+b[i].y-get);
        }
    }
    for(int i=1;i<=cnt;i++)if(!b[i].op)clear(b[i].y);
    for(int i=1;i<=cnt;i++)
    {
        if(!b[i].op)add(1000001-b[i].y,b[i].x-b[i].y);
        else{
            int get=query(1000001-b[i].y);
            if(get==-1)continue;
            else ans[b[i].op]=min(ans[b[i].op],b[i].x-b[i].y-get);
        }
    }
    for(int i=1;i<=cnt;i++)
        if(!b[i].op)clear(1000001-b[i].y);
    for(int i=cnt;i>=1;i--)
    {
        if(!b[i].op)add(b[i].y,b[i].y-b[i].x);
        else{
            int get=query(b[i].y);
            if(get==-1)continue;
            else ans[b[i].op]=min(ans[b[i].op],-b[i].x+b[i].y-get);
        }
    }
    for(int i=cnt;i>=1;i--)
        if(!b[i].op)clear(b[i].y);
    for(int i=cnt;i>=1;i--)
    {
        if(!b[i].op)add(1000001-b[i].y,-b[i].x-b[i].y);
        else{
            int get=query(1000001-b[i].y);
            if(get==-1)continue;
            else ans[b[i].op]=min(ans[b[i].op],-b[i].x-b[i].y-get);
        }
    }
    for(int i=cnt;i>=1;i--)
        if(!b[i].op)clear(1000001-b[i].y);
}
signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    memset(t,-1,sizeof(t));
    cin>>n>>m;
    q=0;
    for(int i=1;i<=n;i++)
    {
        a[i].op=0;
        cin>>a[i].x>>a[i].y;
        a[i].x++;a[i].y++;
    }
    for(int i=n+1;i<=n+m;i++)
    {
        int op;cin>>op>>a[i].x>>a[i].y;
        a[i].x++;a[i].y++;
        if(op==1)a[i].op=0;
        else 
        {
            a[i].op=++q;
            ans[q]=1e13;
        }
    }
    solve(1,n+m);
    for(int i=1;i<=q;i++)cout<<ans[i]<<'\n';
    return 0;
}