这是一道数据结构题。

前置知识

• K-D Tree

思路

考虑可以把一个弹弓映射成三维空间上 $(x,y,t)$ 的点，查询就变成查询距离 $(x,y,0)$ 曼哈顿距离最近的点，解释一下这为什么是正确的，因为 $x$ 轴距离其实就是起点离弹弓起点的距离，$y$ 轴其实就是终点离弹弓终点的距离，$z$ 就是弹弓时间。

接下来就可以用 K-D Tree 维护了。

Code

#include<bits/stdc++.h>
#define ll long long
#define N 100005
using namespace std;
char mode;
struct node{
	int x,y,z;
	bool operator < (const node &opt) const {
		switch(mode){
			case 'x': return x < opt.x;
			case 'y': return y < opt.y;
			case 'z': return z < opt.z;
		}
	}
} dat[N];
int n,m,x,y,z;
ll ans;
namespace KD_Tree{
	struct node{
		int l,r,x,y,z,ax,ay,az,bx,by,bz;
	} tri[N << 2];
	int root,tot;
	void pushup(int p){
		tri[p].ax = tri[p].bx = tri[p].x;
		tri[p].ay = tri[p].by = tri[p].y;
		tri[p].az = tri[p].bz = tri[p].z;
		if(tri[p].l != 0){
			tri[p].ax = min(tri[p].ax,tri[tri[p].l].ax);
			tri[p].ay = min(tri[p].ay,tri[tri[p].l].ay);
			tri[p].az = min(tri[p].az,tri[tri[p].l].az);
			tri[p].bx = max(tri[p].bx,tri[tri[p].l].bx);
			tri[p].by = max(tri[p].by,tri[tri[p].l].by);
			tri[p].bz = max(tri[p].bz,tri[tri[p].l].bz);
		}
		if(tri[p].r != 0){
			tri[p].ax = min(tri[p].ax,tri[tri[p].r].ax);
			tri[p].ay = min(tri[p].ay,tri[tri[p].r].ay);
			tri[p].az = min(tri[p].az,tri[tri[p].r].az);
			tri[p].bx = max(tri[p].bx,tri[tri[p].r].bx);
			tri[p].by = max(tri[p].by,tri[tri[p].r].by);
			tri[p].bz = max(tri[p].bz,tri[tri[p].r].bz);
		}
	}
	int build(int l,int r,char dep){
		if(l > r){
			return 0;
		}
		int mid = (l + r) >> 1;
		mode = dep;
		nth_element(dat + l,dat + mid,dat + r + 1);
		tri[mid].x = dat[mid].x;
		tri[mid].y = dat[mid].y;
		tri[mid].z = dat[mid].z;
		tri[mid].l = build(l,mid - 1,dep == 'x' ? 'y' : (dep == 'y' ? 'z' : 'x'));
		tri[mid].r = build(mid + 1,r,dep == 'x' ? 'y' : (dep == 'y' ? 'z' : 'x'));
		pushup(mid);
		return mid;
	}
	ll get_min(int p){
		ll ans = 0;
		if(tri[p].ax > x or tri[p].bx < x){
			ans += min(abs(tri[p].ax - x),abs(tri[p].bx - x));
		}
		if(tri[p].ay > y or tri[p].by < y){
			ans += min(abs(tri[p].ay - y),abs(tri[p].by - y));
		}
		if(tri[p].az > z or tri[p].bz < z){
			ans += min(abs(tri[p].az - z),abs(tri[p].bz - z));
		}
		return ans;
	}
	ll get_dict(int p){
		return abs(tri[p].x - x) + abs(tri[p].y - y) + abs(tri[p].z - z);
	}
	void query(int p){
		if(p == 0 or get_min(p) >= ans){
			return;
		}
		ans = min(ans,get_dict(p));
		int dl = get_min(tri[p].l),dr = get_min(tri[p].r);
		if(dl < dr){
			query(tri[p].l);
			query(tri[p].r);
		}else{
			query(tri[p].r);
			query(tri[p].l);
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for(int i = 1;i <= n;i ++){
		cin >> dat[i].x >> dat[i].y >> dat[i].z;
	}
	KD_Tree::root = KD_Tree::build(1,n,'x');
	while(m --){
		cin >> x >> y;
		z = 0;
		ans = abs(x - y);
		KD_Tree::query(KD_Tree::root);
		cout << ans << '\n';
	}
	return 0;
}