神秘做法。

题目分析

首先很显然的是，当 $A$ 增大的时候，$B$ 一定不增。

注意到题目中有一个很重要的条件：保证任意两条线路除端点外没有其他公共点，说明这是一个平面图。

平面图有什么性质呢？我们不妨只考察第一个系统。容易发现，对于其上的枢纽 $(X,Y)$，当仅保留 $y \le Y$ 的枢纽时，能到达的村庄是一个区间。所以问题可以转化成：平面上有几条平行于横轴的线段，对于每个上界求出一个最大的下界使得里面的线段的横坐标并为整个区间。（线段包含或不交貌似并没什么用？）

考虑怎么求区间。考虑沿纵轴扫描线，逐个加入点。对于一个点，可以到达的区间是相邻点所在连通块区间的并。并查集维护即可。

“横坐标并为整个区间”需要更好的刻画方式。联想成有 $n$ 个城市，中间有 $n-1$ 条道路，一条线段就是让上面道路可以经过。所以我们维护每条道路的覆盖次数，最小值为 $0$ 则不合法，否则合法。线段树维护即可。

$O(n \log n)$。

Code

#include<bits/stdc++.h>
//bool Mst;
using namespace std;
using ll=long long;
using ld=long double;
//#define int ll
using pii=pair<int,int>;
const int N=2e5+5;
struct dsu
{
	int fa[N];
	void init(int n){for(int i=1;i<=n;i++)fa[i]=i;}
	int f(int x){return fa[x]==x?x:fa[x]=f(fa[x]);}
	void m(int x,int y){if(f(x)!=f(y))fa[f(x)]=f(y);}
}s;
pii operator+(pii x,pii y)
{
	if(!x.first) return y;
	if(!y.first) return x;
	return {min(x.first,y.first),max(x.second,y.second)};
}
struct tree
{
	int n,m;
	vector<int> g[N];
	int x[N],y[N],b[N];pii seg[N];
	vector<int> vec[N];
	void read(int sign=1)
	{
		for(int i=1;i<=n;i++) x[i]=i,y[i]=0;
		for(int i=n+1;i<=n+m;i++) cin>>x[i]>>y[i],y[i]*=sign;
		for(int i=1,op,u,v;i<n+m;i++)
		{
			cin>>op>>u>>v,v+=n;
			if(op==2) u+=n;
			g[u].push_back(v),g[v].push_back(u);
		}
	}
	void getseg()
	{
//		cout<<"getseg()\n";
		for(int i=n+1;i<=n+m;i++) b[i-n]=y[i];
		sort(b+1,b+m+1);
		b[m+1]=1e9+5;
		for(int i=n+1;i<=n+m;i++) y[i]=lower_bound(b+1,b+m+1,y[i])-b;
//		for(int i=n+1;i<=n+m;i++) cout<<y[i]<<" ";
//		cout<<"\n";
		for(int i=n+1;i<=n+m;i++) vec[y[i]].push_back(i);
		s.init(n+m);
		for(int i=1;i<=n;i++) seg[i]={i,i};
		for(int p=1;p<=m;p++)
			for(int u:vec[p])
				for(int v:g[u]) if(y[v]<=y[u])
					seg[u]=seg[u]+seg[s.f(v)],s.m(v,u);
//		for(int i=1;i<=n+m;i++) cout<<seg[i].first<<" "<<seg[i].second<<"\n";
	}
}t1,t2;
struct sgt
{
	int t[N<<2],tag[N<<2];
	inline int ls(int id){return id<<1;}
	inline int rs(int id){return id<<1|1;}
	inline void push_up(int id)
	{
		t[id]=min(t[ls(id)],t[rs(id)]);
	}
	inline void upd(int id,int x)
	{
		tag[id]+=x,t[id]+=x;
	}
	inline void push_down(int id)
	{
		upd(ls(id),tag[id]),upd(rs(id),tag[id]);
		tag[id]=0;
	}
	void build(int id,int nl,int nr)
	{
		tag[id]=0,t[id]=0;
		if(nl==nr) return;
		int m=(nl+nr)>>1;
		build(ls(id),nl,m),build(rs(id),m+1,nr);
	}
	void update(int l,int r,int x,int id,int nl,int nr)
	{
		if(l<=nl&&r>=nr) return upd(id,x),void();
		push_down(id);
		int m=(nl+nr)>>1;
		if(l<=m) update(l,r,x,ls(id),nl,m);
		if(r>m) update(l,r,x,rs(id),m+1,nr);
		push_up(id);
	}
	int query(){return t[1];}
}tr;
int ans[N];
//bool Med;
signed main()
{
//	cerr<<"Memory Size: "<<abs((&Med)-(&Mst))/1024.0/1024<<" MB\n";
//	freopen("in.in","r",stdin);
//	freopen("out.out","w",stdout);
	int n,m1,m2,q;
	cin>>n>>m1>>m2>>q;
	t1.n=n,t1.m=m1,t2.n=n,t2.m=m2;
	t1.read(),t2.read(-1);
	t1.getseg(),t2.getseg();
#define all 1,1,n-1
	tr.build(all);
	auto upd=[&](pii p,int x)->void
	{
		auto [l,r]=p;
		if(l>=r) return;
		r--;
		tr.update(l,r,x,all);
	};
	for(int i=1;i<=n+m2;i++) upd(t2.seg[i],1);
	for(int p=0,q=m2;p<=m1;p++)
	{
		for(int i:t1.vec[p]) upd(t1.seg[i],1);
		while(q>=0&&tr.query())
		{
			for(int i:t2.vec[q]) upd(t2.seg[i],-1);
			q--;
		}
		ans[p]=q+1;
	}
//	for(int i=1;i<=m1;i++) cout<<ans[i]<<" ";
//	cout<<"\n";
	while(q--)
	{
		int x;
		cin>>x;
		int p=upper_bound(t1.b+1,t1.b+m1+2,x)-t1.b-1;
		cout<<-t2.b[ans[p]]<<"\n";
	}
	return 0;
}