C++ 解法, 执行用时: 3574ms, 内存消耗: 55132K, 提交时间: 2021-07-18 20:37:15

#include<iostream>
#include<cstring>
using namespace std;
#define lowbit(x) ((x)&(-x))
const int N = 1e6+10;
struct node{
	int x,y,f,id;
}a[N],b[N],c[N];
int n,m,cnt;
int tr[N],M=-1e9;
void add(int x,int v){for(int i=x;i<=M;i+=lowbit(i)) tr[i] = max(tr[i],v);}
int query(int x){int res = 0;for(int i=x;i;i-=lowbit(i)) res=max(res,tr[i]); return res;}
void cls(int x){for(int i=x;i<=M;i+=lowbit(i)) tr[i]=0;}

int num[N],ans[N];
void CDQ(int ll,int rr){
	if(ll==rr) return;
	int mid = (ll+rr)>>1;
	CDQ(ll,mid),CDQ(mid+1,rr);
	
	int t1=ll,t2=mid+1,p=ll;
	while(t2<=rr){
		while(t1<=mid&&a[t1].x<=a[t2].x){
			if(a[t1].f==1) add(a[t1].y,a[t1].x+a[t1].y);
			b[p++]=a[t1++];
		}
		if(a[t2].f==2){
			int tt = query(a[t2].y);
			if(tt) ans[a[t2].id] = min(ans[a[t2].id],a[t2].x+a[t2].y-tt);
		}
		b[p++]=a[t2++];
	}
	for(int i=ll;i<t1;i++) cls(a[i].y);
	
	while(t1<=mid) b[p++]=a[t1++];
    while(t2<=rr) b[p++]=a[t2++];
    for(int i=ll;i<=rr;++i) a[i]=b[i];
	
}

void init(int d){
	int mxx=0,myy=0;cnt=0;
	for(int i=1;i<=n+m;i++){
		if(d==1) c[i].x = M-c[i].x;
		else if(d==2) c[i].y = M-c[i].y;
		if(c[i].f==2) mxx=max(mxx,c[i].x),myy=max(myy,c[i].y);
	}
	for(int i=1;i<=n+m;i++){
		if(c[i].x<=mxx&&c[i].y<=myy) a[++cnt] = c[i];
	}
}

int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		c[i].id=i,c[i].f=1;
		scanf("%d%d",&c[i].x,&c[i].y);
		c[i].x++,c[i].y++;
		M = max(M,max(c[i].x,c[i].y));
	}
	for(int i=n+1;i<=n+m;i++){
		scanf("%d%d%d",&c[i].f,&c[i].x,&c[i].y);
		c[i].id = i;
		c[i].x++,c[i].y++;
		if(c[i].f==2) num[++num[0]] = i;ans[i] = 1e9;
		M = max(M,max(c[i].x,c[i].y));
	}
	M++;
	init(0),CDQ(1,cnt);
	init(1),CDQ(1,cnt);
	init(2),CDQ(1,cnt);
	init(1),CDQ(1,cnt);
	for(int i=1;i<=num[0];i++) printf("%d\n",ans[num[i]]);
	
	return 0;
}