CF1550F Jumping Around 题解 / Boruvka 学习笔记

zrl123456 · 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