upd 2025/12/27：贴了两张图，补了一个证明，改了几个变量名，修正了几处笔误，优化了排版。

---

官解做法，但是更详细。

:::info[题意转化]{open}

为避免变量名重复，用 $x,y$ 代替题面中的 $a,b$。

给定两个大小分别为 $n,m$ 的集合 $A,B$。考虑按如下方式建立图 $G_A,G_B$：

• 对于 $A$ 中的每个元素 $a_i$，其在 $G_A$ 中向所有满足 $a_i+x \ge a_j$ 的元素 $a_j$ 连一条边；
• 对于 $B$ 中的每个元素 $b_i$，其在 $G_B$ 中向所有满足 $b_i+y \ge b_j$ 的元素 $b_j$ 连一条边。

分别从 $a_1,b_1$ 开始，沿边移动，最终抵达 $a_n,b_m$，求两条路径上的元素组成集合的大小的最小值。

:::

暴力

记 $C=A \cap B$，大小为 $k$，且 $c_1=0$，$c_k=L$。

定义 $f_{i}$ 为两条路径都走到 $c_i$ 时的答案。记 $d_A(c_j,c_i)$ 为在 $A$ 中从 $c_j$ 走到 $c_i$ 的最少步数，$d_B(c_j,c_i)$ 同理。则转移为

$$f_i=\min\limits_{j<i}\{f_j+d_A(c_j,c_i)+d_B(c_j,c_i)-1\}$$

暴力计算 $d_A,d_B$。复杂度 $O(n^2)$。

优化

一个比较显然的结论是，每次沿边移动时，我们都会跳得尽可能远。也就是说，若当前位于 $a_i$，则跳到满足 $a_i+x \ge a_j$ 的最大 $a_j$ 一定是最优的。$b_i$ 同理。

这样一来，原先的图便变成了树。无解的情况即为不连通。记两棵树分别为 $T_A,T_B$。

考虑上面的朴素做法为什么不行。是因为直接暴力地算 $d_A,d_B$ 太慢了，对吧？于是考虑结合上面的性质进行优化。

以 $d_A$ 为例。我们想要在 $T_A$ 中从 $c_j$ 走到 $c_i$，最理想的情况为 $c_i$ 是 $c_j$ 的祖先，这样直接跳树边就是最优解（如下图所示）。

:::align{center}

:::

此时

$$d_A(c_j,c_i)=\text{dep}_A(c_j)-\text{dep}_A(c_i)$$

其中 $\text{dep}_A(i)$ 表示节点 $i$ 在 $T_A$ 中的深度。

然而并非所有情况都是理想的。如果 $c_i$ 不是 $c_j$ 的祖先呢？此时，我们会先按上述策略跳到一个与 $c_i$ 深度相同的节点 $u$ 上，再从这个节点跳到 $c_i$（如下图所示）。

:::align{center}

:::

此时

$$d_A(c_j,c_i)=\text{dep}_A(c_j)-\text{dep}_A(c_i)+1$$

:::info[为什么一定可以这样跳呢？]{open}

首先，树上的节点只会指向权值比自己大的节点。这是显然的。那么，如果节点 $u$ 可以跳到自己的父亲 $v$，说明 $u+x \ge v$。由于 $v>c_i$，$u+x \ge c_i$ 也一定成立。故 $u$ 一定可以跳到 $c_i$。

:::

综上，我们可以引入一个偏差量 $\varepsilon_A(c_j,c_i) \in \{0,1\}$，使得

$$d_A(c_j,c_i)=\text{dep}_A(c_j)-\text{dep}_A(c_i)+\varepsilon_A(c_j,c_i)$$

于是，我们记 $g_i=f_i+\text{dep}_A(c_i)+\text{dep}_B(c_i)$。将上式带入前面的暴力转移，移项并化简，得

$$g_i=\min\limits_{j<i}\{g_j+\varepsilon_A(c_j,c_i)+\varepsilon_B(c_j,c_i)-1\}$$

转移的过程中，我们遍历 $i=1,2,\dots,k$。记 $\text{ans}_i$ 为此时的答案。我们发现，由于 $\varepsilon_A,\varepsilon_B \in \{0,1\}$，$\text{ans}_i$ 只有 $\text{ans}_{i-1}-1$，$\text{ans}_{i-1}$ 和 $\text{ans}_{i-1}+1$ 三种取值。

考虑三种转移分别对应哪种情况。

:::info[Case 1：$\mathbf{ans_i=ans_{i-1}-1}$]{open}

此时，$g_j=\text{ans}_{i-1}$ 且 $\varepsilon_A(c_j,c_i)=\varepsilon_B(c_j,c_i)=0$，则 $c_i$ 在 $T_A,T_B$ 中均为 $c_j$ 的祖先。记 $\text{id}_A(i)$ 为节点 $i$ 在 $T_A$ 中的 dfs 序，$\text{id}_B(i)$ 同理，则 $\text{id}_A(i)<\text{id}_A(j)$ 且 $\text{id}_B(i)<\text{id}_B(j)$。

:::

:::info[Case 2：$\mathbf{ans_i=ans_{i-1}}$]{open}

此时，有两种情况。

要么，$g_j=\text{ans}_{i-1}$，$\varepsilon_A(c_j,c_i)+\varepsilon_B(c_j,c_i)=1$，则 $\text{id}_A(i)<\text{id}_A(j)$ 或 $\text{id}_B(i)<\text{id}_B(j)$。

要么，$g_j=\text{ans}_{i-1}+1$，$\varepsilon_A(c_j,c_i)=\varepsilon_B(c_j,c_i)=0$，则 $\text{id}_A(i)<\text{id}_A(j)$ 且 $\text{id}_B(i)<\text{id}_B(j)$。

:::

:::info[Case 3：$\mathbf{ans_i=ans_{i-1}+1}$]{open}

若上述所有条件均不成立，则为此种情况。

:::

上述有关 $g_j$ 的限制，可以搞两棵线段树，一棵维护满足 $g_j=\text{ans}_{j-1}$ 的点 $j$，另一棵维护满足 $g_j=\text{ans}_{j-1}+1$ 的点 $j$。$\text{id}_A,\text{id}_B$ 的限制均为二维偏序问题，由于值域较小，可以在线段树上简单地处理。这样说可能有点模糊，可以结合代码理解。

至此，问题在 $O(n \log n)$ 的复杂度内解决。

代码

:::success[官解查重率 100%]

#include <bits/stdc++.h>
#define lson (u << 1)
#define rson ((u << 1) | 1)
#define mid ((l + r) >> 1)
using namespace std;
typedef long long ll;
const int MAXN = 1e6 + 10;
int n, m, k, xa[MAXN], xb[MAXN], nxta[MAXN], nxtb[MAXN], ida[MAXN], idb[MAXN], g[MAXN], tmp;
ll ta[MAXN], tb[MAXN], l, a, b;
vector <int> adja[MAXN], adjb[MAXN];
struct Segment_tree{
	int mx[MAXN << 2];
	void pushup(int u){
		mx[u] = max(mx[lson], mx[rson]);
		return;
	}
	void build(int u, int l, int r){
		if (mx[u] == 0){
			return;
		}
		if (l == r){
			mx[u] = 0;
			return;
		}
		build(lson, l, mid);
		build(rson, mid + 1, r);
		pushup(u);
		return;
	}
	void modify(int u, int l, int r, int pos, int x){
		if (l == r){
			mx[u] = x;
			return;
		}
		if (pos <= mid){
			modify(lson, l, mid, pos, x);
		}
		else{
			modify(rson, mid + 1, r, pos, x);
		}
		pushup(u);
		return;
	}
	int query(int u, int l, int r, int ql, int qr){
		if (ql <= l && r <= qr){
			return mx[u];
		}
		int maxn = 0;
		if (ql <= mid){
			maxn = max(maxn, query(lson, l, mid, ql, qr));
		}
		if (qr > mid){
			maxn = max(maxn, query(rson, mid + 1, r, ql, qr));
		}
		return maxn;
	}
}tmp0, tmp1, *tr0 = &tmp0, *tr1 = &tmp1;
void init(){
	int curi = 1, curj = 1;
	while (curi <= n && curj <= m){
		if (ta[curi] < tb[curj]){
			curi++;
		}
		else if (ta[curi] > tb[curj]){
			curj++;
		}
		else{
			k++;
			xa[k] = curi;
			xb[k] = curj;
			curi++;
			curj++;
		}
	}
	return;
}
void solve_nxt(int len, ll *tc, int *nxtc, ll c){
	for (int i = 1, j = 1; i < len; i++){
		while (j <= len && tc[j] <= tc[i] + c){
			j++;
		}
		if (j <= i + 1){
			cout << "-1" << endl;
			exit(0);
		}
		nxtc[i] = j - 1;
	}
	return;
}
void build_tree(int len, int *nxtc, vector <int> *adjc){
	for (int i = 1; i < len; i++){
		adjc[nxtc[i]].push_back(i);
	}
	return;
}
void solve_id(int &cur, int u, vector <int> *adjc, int *idc){
	idc[u] = ++cur;
	for (int v : adjc[u]){
		solve_id(cur, v, adjc, idc);
	}
	return;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> l >> a >> b;
	for (int i = 1; i <= n; i++){
		cin >> ta[i];
	}
	for (int i = 1; i <= m; i++){
		cin >> tb[i];
	}
	init();
	solve_nxt(n, ta, nxta, a);
	solve_nxt(m, tb, nxtb, b);
	build_tree(n, nxta, adja);
	build_tree(m, nxtb, adjb);
	tmp = 0; solve_id(tmp, n, adja, ida);
	tmp = 0; solve_id(tmp, m, adjb, idb);
	tr0 -> build(1, 1, n);
	tr1 -> build(1, 1, n);
	g[1] = 1;
	for (int i = 1; i < n; i = nxta[i]){
		g[1]++;
	}
	for (int i = 1; i < m; i = nxtb[i]){
		g[1]++;
	}
	int gmin = g[1];
	tr0 -> modify(1, 1, n, ida[xa[1]], idb[xb[1]]);
	for (int i = 2; i <= k; i++){
		if (tr0 -> query(1, 1, n, ida[xa[i]], n) > idb[xb[i]]){
			gmin--;
			g[i] = gmin;
			swap(tr0, tr1);
			tr0 -> build(1, 1, n);
			tr0 -> modify(1, 1, n, ida[xa[i]], idb[xb[i]]);
		}
		else if (tr0 -> query(1, 1, n, 1, n) > idb[xb[i]] || tr0 -> query(1, 1, n, ida[xa[i]], n) > 0 || tr1 -> query(1, 1, n, ida[xa[i]], n) > idb[xb[i]]){
			g[i] = gmin;
			tr0 -> modify(1, 1, n, ida[xa[i]], idb[xb[i]]);
		}
		else{
			g[i] = gmin + 1;
			tr1 -> modify(1, 1, n, ida[xa[i]], idb[xb[i]]);
		}
	}
	cout << g[k] << endl;
	return 0;
}

:::

后记

有史以来写题解最用心的一次了。越来越觉得这是一种很有效的学习方法了。在写这篇题解的过程中，我把自己 AC 时没做的证明都补上了，也对这题有了更深刻的理解。如果不经历这个过程的话，恐怕只是对着官解敲了一遍代码吧。

最后看在我熬夜写题解的份上，能点个赞吗？祝你新年快乐喵！