CDQ分治

没用快读快写82ms,目前全ACGO跑的最快

#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
const int M=2000005;
const int INF=2e9;
struct query{
    int x,y;
    int id,type;
    int ans;
}a[N],b[N],tmp[N];
int n,m,len;
int x,y;
int s[M];
int lowbit(int x){
    return x&-x;
}
void update(int x,int d){
    for(int i=x;i<=len;i+=lowbit(i)) s[i]=max(s[i],d);
}
int ask(int x){
    int ans=0;
    for(int i=x;i;i-=lowbit(i)) ans=max(ans,s[i]);
    return ans?ans:-INF;
}
void clear(int x){
    for(int i=x;s[i];i+=lowbit(i)) s[i]=0;
}
void cdq(int l,int r){
    if(l==r) return;
    int mid=(l+r)/2;
    cdq(l,mid);
    cdq(mid+1,r);
    int t1=l,t2=mid+1;
    int k=l;
    while(t2<=r){
        while(t1<=mid&&b[t1].x<=b[t2].x){
            if(b[t1].type==1) 
                update(b[t1].y,b[t1].x+b[t1].y);
            tmp[k++]=b[t1++];
        }
        if(b[t2].type==2){
            int id=b[t2].id,res=ask(b[t2].y);
            a[id].ans=min(a[id].ans,b[t2].x+b[t2].y-res);
        }
        tmp[k++]=b[t2++];
    }
    for(int i=l;i<t1;i++)
        if(b[i].type==1) clear(b[i].y);
    while(t1<=mid) tmp[k++]=b[t1++];
    for(int i=l;i<=r;i++) b[i]=tmp[i];
}
void solve(int nx,int ny){
    for(int i=1;i<=n+m;i++){
        b[i]=a[i];
		if(nx) b[i].x=len-b[i].x;
		if(ny) b[i].y=len-b[i].y;
    }
    cdq(1,n+m);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int x,y;
        cin>>x>>y;
        x++,y++;
        a[i]={x,y,i,1,INF};
        len=max(len,max(x,y));
    }
    for(int i=1;i<=m;i++){
        int t,x,y;
        cin>>t>>x>>y;
        x++,y++;
        a[i+n]={x,y,i+n,t,INF};
        len=max(len,max(x,y));
    }
    len++;
    solve(0,0);
    solve(1,0);
    solve(0,1);
    solve(1,1);
    for(int i=n+1;i<=n+m;i++)
        if(a[i].type==2) cout<<a[i].ans<<endl;
    return 0;
}