本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-17 20:35:58

:::::info[闲话] 我咋从来没写过 Boruvka 的题，菜完了。
::::: :::::info[题目基本信息] 考察：最小生成树，并查集（$2700$）。
题目简介：
一个数轴上有 $n$ 个点，位置编号构成序列 $\{a_n\}$，现在你可以从 $i$ 点跳跃到 $j$ 点，跳跃条件为：

• 有常数 $d,k$，要求 $|a_i-a_j|\in[d-k,d+k]$。

给定 $s,d$，$q$ 次询问，每次给出 $t,k$，问 $s$ 能否通过若干次跳跃移动到 $t$ 上。
数据范围：

• $1\le n,q\le 2\times 10^5$
• $1\le s,t\le n$
• $1\le d,k\le 10^6$
• $\forall i\in[1,n],1\le a_i\le 10^6$ ::::: 容易发现 $k$ 是满足单调性的，更具体地，若 $k$ 满足条件则 $k+1$ 一定满足条件，若 $k$ 不满足条件则 $k-1$ 一定满足条件。所以我们想到预处理每个 $t$ 的分界点。
  要求 $k$ 最小，也就是 $\forall i,j$ 在路径中，要求 $||a_i-a_j|-d|$ 最小，不妨以 $||a_i-a_j|-d|$ 为边权给 $i,j$ 连边，这样就形成了一个图，最后答案就是该图的最小生成树上的路径的边权最大值。
  边权有特殊性质的完全图最小生成树，我们考虑使用 Boruvka。
  :::::success[Boruvka 讲解] 具体地，我们称以下过程为 $1$ 轮：

1. 给每个点找到和它距离最近的点。
2. 将每个点与离它距离最近的点缩成一个点。

进行若干轮这样的操作直到只剩一个点。
::::success[正确性] 容易发现第 1 步类似 Kruskal，第 2 步类似 Prim，Boruvka 的正确性可以通过前两者的正确性（不知道是不是严谨地）推出。
:::: ::::success[复杂度] 容易发现 $1$ 轮最坏情况下是这些点两两配对，点数减少一半，所以设 $T$ 为给每个点找到和它距离最近的点的时间复杂度，那么总时间复杂度就为 $\Theta(n\log n\cdot T)$。
:::: ::::: 本题中套用 Boruvka，容易发现可以使用双指针的方式找到与 $a_i+d$ 和 $a_i-d$ 最接近的点，所以本题均摊下 $T=\Theta(1)$。
然后做完了。
时间复杂度为 $\Theta(n\log n+q)$，空间复杂度为 $\Theta(n)$。

code