rt，用的排序+动态开点线段树

枚举 2 次，725ms/1000ms，95.27mb/125.00mb，AC

枚举 4 次，1200ms/1000ms，51.25mb/125.00mb

求调枚举 4 次的代码

#include<bits/stdc++.h>
#define ls x->lc
#define rs x->rc
using namespace std;
typedef long long ll;
const int N=1e5+5;
int n,m;
ll ans[N];
struct op{
	ll x,y,t,id;
}q[N<<1];
struct node{
	ll mn;
	node*lc,*rc;
	node(){
		mn=1e18;
		lc=rc=NULL;
	}
}*rt;
void up(node*&x){
	x->mn=1e18;
	if(ls!=NULL){
		x->mn=min(x->mn,ls->mn);
	}
	if(rs!=NULL){
		x->mn=min(x->mn,rs->mn);
	}
}
void insert(node*&x,int l,int r,int k,int v){
	if(x==NULL){
		x=new node;
	}
	if(l^r){
		int mid=(l+r)>>1;
		if(k<=mid){
			insert(ls,l,mid,k,v);
		}else{
			insert(rs,mid+1,r,k,v);
		}
		up(x);
	}else{
		x->mn=v;
	}
}
ll query(node*x,int l,int r,int ql,int qr){
	if(x==NULL||ql>qr){
		return 1e18;
	}
	if(ql<=l&&r<=qr){
		return x->mn;
	}
	int mid=(l+r)>>1;
	ll ret=1e18;
	if(ql<=mid){
		ret=min(ret,query(ls,l,mid,ql,qr));
	}
	if(qr>mid){
		ret=min(ret,query(rs,mid+1,r,ql,qr));
	}
	return ret;
}
void erase(node*&x){
	if(x==NULL){
		return;
	}
	erase(ls);
	erase(rs);
	delete[]x;
	x=NULL;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%lld%lld%lld",&q[i].x,&q[i].y,&q[i].t);
		q[i].id=0;
	}
	for(int i=1;i<=m;++i){
		scanf("%lld%lld",&q[i+n].x,&q[i+n].y);
		ans[q[i+n].id=i]=abs(q[i+n].x-q[i+n].y);
	}
	sort(q+1,q+n+m+1,[](op u,op v){return u.x^v.x?u.x<v.x:u.id<v.id;});
	rt=NULL;
	for(int i=1;i<=n+m;++i){
		if(q[i].id){
			ans[q[i].id]=min(ans[q[i].id],q[i].x+q[i].y+query(rt,0,1e9,0,q[i].y));
		}else{
			insert(rt,0,1e9,q[i].y,q[i].t-q[i].y-q[i].x);
		}
	}
	erase(rt);
	for(int i=1;i<=n+m;++i){
		if(q[i].id){
			ans[q[i].id]=min(ans[q[i].id],q[i].x-q[i].y+query(rt,0,1e9,q[i].y+1,1e9));
		}else{
			insert(rt,0,1e9,q[i].y,q[i].t+q[i].y-q[i].x);
		}
	}
	erase(rt);
	for(int i=n+m;i;--i){
		if(q[i].id){
			ans[q[i].id]=min(ans[q[i].id],q[i].y+query(rt,0,1e9,0,q[i].y)-q[i].x);
		}else{
			insert(rt,0,1e9,q[i].y,q[i].x+q[i].t-q[i].y);
		}
	}
	erase(rt);
	for(int i=n+m;i;--i){
		if(q[i].id){
			ans[q[i].id]=min(ans[q[i].id],query(rt,0,1e9,q[i].y+1,1e9)-q[i].x-q[i].y);
		}else{
			insert(rt,0,1e9,q[i].y,q[i].x+q[i].t+q[i].y);
		}
	}
	erase(rt);
	for(int i=1;i<=m;++i){
		printf("%lld\n",ans[i]);
	}
}