排序破随机，倍增压长途——传送门最短距离的 O(n log n) 绝杀

前情提要

《数字大陆》的策划上次被你一句“图论是障眼法，数组才是本体”打击得不轻。据说那天下午，他一个人坐在会议室里，盯着美术画了三天的传送门网络图发了整整半小时呆。

今天，他重新出现在你桌边，眼圈比昨天深了两个色号：“上次那个需求——” 他清了清嗓子，“确实……稍微简单了一点。”

你抬头看了他一眼。

策划迅速补充：“但这次不一样！这次我认真设计了！”

他“啪”地把一份新需求拍在桌上——新版本里，勇者试炼不再是一条规规矩矩的战力长廊。策划吸取了你的建议，把所有关卡彻底打乱：编号 0 的可能是灭世魔龙，编号 1 的可能是史莱姆，编号 2 又可能是深渊领主。总之，怪物战力 nums[i] 和关卡编号再也没有任何顺序关系。

传送门的生成规则倒是没变：

如果两个关卡的怪物战力之差不超过 maxDiff，它们之间就会生成一条双向传送门。

你点了点头：“所以还是查询两个节点是否连通？”

“不。” 策划脸上露出了“这次你总不能秒杀了吧”的笑容，“现在玩家不仅要知道能不能到，还要知道最少经过几扇传送门。”

他指着需求文档上的一行加粗文字：

对于每个查询 [u, v]，返回节点 u 到节点 v 的最短距离；如果无法到达，则返回 -1。

“玩家现在很讲究效率。”策划解释道，“萌新想少过几次加载界面，肝帝想研究最短刷图路线，速通玩家则表示多传送一次都是对世界纪录的侮辱。”

你沉默了两秒。

策划得意地抱起胳膊：“怎么样？这次总得老老实实建图跑最短路了吧？”

你没有回答，只是低头看向数据范围。

每次 BFS？服务器听完连夜跑路

最直接的方案确实是建图——对于所有节点对 (i, j)，如果满足|nums[i] - nums[j]| <= maxDiff，就在它们之间连一条无向边。图建好之后，每条查询从 u 出发跑一次标准 BFS，第一次到达 v 时的层数就是最短距离。

理论很标准，代码很正统，复杂度更是十分感人——n ≤ 10⁵，暴力枚举节点对建图就是 O(n²)，更要命的是，如果大量节点的战力值都很接近，这张图会趋近于一张完全图，边数同样直冲 O(n²)，然后你还要在这个庞然大物上跑10⁵次 BFS——这已经不只是超时的问题了，你的开发机会在按下回车的瞬间火箭式升温，公司当月的电费账单上会单独列一行你的名字。

你赶紧把“建完全图 + 全量 BFS”的方案丢进脑海中的回收站，顺手清空以防自己手贱还原。

数据范围不会说谎——n 和 queries 都是 10⁵ 级别，这意味着你需要 O(n log n) 以内的预处理，和 O(1) 或 O(log n) 的单次查询。

编号是乱的，但可以重新排队

策划只说 nums 没有排序，又没说我们不能自己排。

虽然策划把关卡编号搅成了一锅粥：0 号位蹲着战力 99999 的灭世魔龙，1 号位是战力 5 的史莱姆幼儿园，2 号位又变成战力 50 的精英怪，主打一个精神分裂式排列。但他忘了一条基本法——传送门只认战力差——战力值才是真正决定谁和谁能互相串门的社交属性。

你脑子里冒出一个非常自然的想法：

“那我把它们按战力重新排个队不就行了？”

于是，你祭出排序大法。把所有节点按战力从小到大排好，再用一个 pos 数组记下每个原节点排序后去了哪个新位置——毕竟查询给你的还是原来的编号 [u, v]。

# 按战力排序，order[k] 表示排序后第 k 个位置对应的原节点
idx = sorted(range(n), key=lambda i: nums[i])

# values：排序后的战力数组
values = [nums[node] for node in idx]

# pos[node]：原节点 node 在排序后数组里所在的位置
pos = [0] * n
for rank, node in enumerate(idx):
    pos[node] = rank

例如，原来的节点顺序是：

节点编号： 0    1    2
战力值： 99999  5   50

排序后就变成：

排序位置： 0    1     2
原节点：   1    2     0
战力值：   5   50   99999

于是：

pos[1] = 0
pos[2] = 1
pos[0] = 2

现在，任意原始查询 [u, v] 只需要做一次“花名册翻译”：

l, r = pos[u], pos[v]
if l > r:
    l, r = r, l

这么一来，原本被策划打乱的关卡，又按照战力整整齐齐地站成了一排。战力相近的节点重新成为邻居，昨天那条熟悉的副本长廊仿佛又回来了。

贪心+双指针：给每个关卡测量最大传送距离

“能一步跳得更远，为什么要故意跳近？”

你重新审视排序后的战力数组：对于位置 i，如果它能直接跳到右侧某个位置 j（即 values[j] - values[i] <= maxDiff），那么夹在 i 和 j 之间的所有位置，i 也全都能一步到达。

原因很朴素——数组 values 已经有序，values[i] <= values[k] <= values[j]，战力差只会更小，传送门全部畅通。也就是说，每个节点向右能直接到达的节点，一定构成一段连续区间，绝不会有“能跳到第 5 关却跳不到第 3 关”的玄学bug。

盯着这条性质，你很快想到——既然目标是找最短距离，那么对于这张看似边数爆炸的图，你根本不需要记每个节点 i 具体能跳到中间哪些位置，只需要记一个——从这里出发，一步最远能跳到哪个位置？ 剩下的全在射程之内，多记一笔都是对内存的不尊重。

你给这个最远位置起了个名字叫 farthest[i]。对于每个节点 i，找到最大的 j，使得 values[j] - values[i] <= maxDiff。因为 values 已经有序，当 i 向右移动时，满足条件的最右j也只会单调右移，不会回缩。一枚滑动窗口，左指针推着右指针走，O(n) 时间就能把整个 farthest 数组填满。

right = 0
for left in range(n):
    right = max(right, left)
    while (right + 1 < n and values[right + 1] - values[left] <= maxDiff):
        right += 1
    farthest[left] = right  # f[i] = 从 i 跳 1 步能到达的最右位置

不过，久经沙场的你意识到一个问题——如果想知道从节点 0 到节点 12 最少要几步，难道要老老实实模拟“跳一步 → 看落点 → 再跳一步 → 再看落点 → …”？！

单次查询还好说，最坏情况下每次只往右挪一格，跳完一整条长廊需要 O(n) 步。但外面有十万次查询正排着队，O(n) 乘十万就是 O(n²) ，复杂度的噩梦换了件马甲又来了。

你把冰美式往桌上重重一顿——你需要一种更聪明的“跳步”技巧。

倍增：给传送技能装上连招系统

你靠在椅背上，盯着那条战力曲线和 farthest 数组，脑子里翻出了压箱底的老伙计——倍增。这个名字听起来像健身房术语，但它的核心思想非常炫酷：

与其一步一步数着传送次数往前挪，不如提前算好“跳 1 步最远到哪、跳 2 步最远到哪、跳 4 步最远到哪、跳 8 步最远到哪……”，把这些结果存成一张速查表。查询的时候从大步开始试，能跨一大步绝不碎步挪，用对数级的时间把距离凑出来。

就像 RPG 里赶路——能骑飞龙绝不下地跑，能开传送阵绝不腿着去。你现在的任务，就是给每个节点建一张“飞龙航班表”。

前面你已经拿到了跳一步（2⁰ = 1）的最远射程 farthest[i][0]。现在想知道多步能跳多远？很简单：两步就是一步再一步、四步就是两步再两步……状态转移直接得就像在技能树上点“二段跳”天赋——从 i 跳 2^k 步，可以先跳 2^(k-1) 步到一个中间落脚点，再从那里接着跳 2^(k-1) 步。两段接力，步数翻倍，射程指数级爆炸。

于是你重新定义了一张二维表 farthest[i][k]：表示从位置 i 出发，跳 2^k 步之后最远能到达的位置。递推公式一行搞定farthest[i][k] = farthest[ farthest[i][k-1] ][k-1]：

• k = 0 是跳 1 步（2⁰ = 1）：就是刚才算的一步最远射程 farthest，每个节点一步能直接传送到的最关关卡。
• k = 1 是跳 2 步（2¹ = 2）：先从 i 跳一步到 farthest[i][0]，再从这个落点跳一步到 farthest[ farthest[i][0] ][0]。两步接力，就是从 i 出发跳两步能覆盖的最远范围。
• k = 2 是跳 4 步：先跳两步到 farthest[i][1]，再从那里跳两步到 farthest[ farthest[i][1] ][1]。以此类推。

m = (n).bit_length()  # m=log2(n)+1，表示倍增的最大层数；如n=5时，m=3，表示最多可以跳2^2=4步
farthest = [[0] * m for _ in range(n)]

# k = 0：一步最远射程（双指针滑动窗口）
right = 0 
for left in range(n): 
    right = max(right, left) 
    while (right + 1 < n and values[right + 1] - values[left] <= maxDiff ): 
        right += 1 
    farthest[left][0] = right	# f[i][0] = 从 i 跳 1 步能到达的最右位置

# k >= 1：两段拼接，指数级扩展
for k in range(1, m):
    for i in range(n):
        farthest[i][k] = farthest[farthest[i][k-1] ][k-1]
        # 状态转移方程：从i跳2^j步 = 先从i跳2^(j-1)步到中间点，再从中间点跳2^(j-1)步

建完这张表，你感觉自己像个在机房里偷偷装加速器的网管——每个节点现在都自带一张“飞龙航班时刻表”，从跳 1 步到跳 2^k 步的最远落点，一查就有。

查询：从大步开始试，能跨一大步绝不碎步挪

表建好了，真正的表演现在开始。

对于每个查询 [l, r]（已经转换成排序后的新位置，且保证 l <= r），你要回答从 l 出发，最少跳几步能到达或越过 r。

策略就是贪心 + 倒序枚举——从最大的 k 开始往下试：如果从当前位置跳 2^k 步还够不着 r（即 farthest[cur][k] < r），那就毫不犹豫把这 2^k 步全吞下去——当前位置更新为 farthest[cur][k]，步数累加 2^k。

因为 k 是从大到小枚举的，每次跳跃都是“在不越过的前提下能跨的最大步”，就像玩大富翁掷骰子，先看看能不能掷出 8 步，不行再退而求其次试 4 步、2 步、1 步。用最少的次数逼近终点。

当所有 k 都试完，你的当前位置 cur 已经停在了 r 之前或恰好等于 r。如果 cur == r，说明刚好到站，当前累加的步数就是答案。如果 cur < r，说明还需要最后一跳——检查 farthest[cur][0] 能不能覆盖 r。如果能，步数加一，返回答案；如果不能，说明 r 在当前位置的最远射程之外，它俩中间有道断崖，返回 -1。

res = []

for u, v in queries:
    l, r = pos[u], pos[v]  			# 将原始节点编号转换为排序后的排名
    if l > r:
        l, r = r, l  				# 保证 l <= r，因为我们只关心从左到右的距离
    if l == r:
        res.append(0)  				# 特殊情况：同一个节点，距离为0
        continue
    step = 0
    for i in range(m - 1, -1, -1):
        if farthest[l][i] < r:
            l = farthest[l][i]  	# 没到r，执行这次跳跃
            step += 1 << i  		# 累加实际跳跃步数（2^i步！）

	if farthest[l][0] >= r:			# 到达或超过r
        res.append(step + 1)  		# 把最后1步加上
    else:
        res.append(-1)  			# 无法到达，不连通

return res

双指针扫 farthest，倍增建表，倒序贪心查询。三步环环相扣，把一张被策划搅乱编号的随机图，重新拉回了 O(n log n) 的可控范围。

尾声

你把结果打包发给策划。不到一分钟，对话框就亮了起来：“这次你总建图了吧？”

“没有。”

“你跑 BFS 了？”

“也没有。”

“那最短路怎么求的？”

你想了想，回复道：“先把所有关卡按照战力重新排队。对每个关卡，只记录它一步最远能传到哪里。查询的时候，每一步都尽可能往远处跳，再用倍增一次跳 1、2、4、8…… 步。”

策划沉默了几秒：“所以我这次设计的传送网络……”

“本质上是一群站在数轴上的节点。”

“最短路……”

“本质上是跳跃游戏。”

“十万次查询……”

“本质上是倍增。”

对话框上方的“正在输入”闪了很久，最后只发来一句：“可这次 nums 明明没有排序！”

“是啊。” 你靠在椅背上，端起已经凉透的咖啡。

“你没排序，我可以自己排。”

本作品采用 知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可。