伪图论真数组：策划想做开放世界，我却发现它只是几个连续副本区

《数字大陆》的策划最近沉迷《只狼》，连着一周每天死五十次之后，他悟了——真正的游戏就该让玩家只能往前，不能回头。于是他拍板在新版本里塞了一张叫“勇者试炼·一条路走到黑”的地图：一条从西到东笔直延伸的长廊，依次排列着 n 个副本关卡，编号 0 到 n-1。每个关卡蹲着一群怪物，战力值用 nums[i] 表示。出于“玩家不能向下碾压”的执念，这条长廊的战力被设计成非递减的——越往东怪越强。西边是战力 5 的史莱姆幼儿园，东边是战力 99999 的灭世魔龙战斗团，中间绝不会有“打完 BOSS 突然冒出三只新手村公鸡”的精神分裂体验。

今天早上，策划端着一杯冰美式准时出现在你工位旁，笑眯眯地把一份需求文档拍在你桌上。

“听我说，这个功能绝了——”他猛吸一口咖啡，“如果两个关卡的怪物战力差距不超过 maxDiff，它们之间就自动生成一条双向传送门。你想啊，战力差不多的副本之间空间稳定性最好，传送门一开，光效一炸，玩家就过去了。要是战力差太多——砰！虚空乱流！玩家直接被撕成像素碎片！我可不想被运营发邮件说‘又有玩家卡进地板了’。”

他完全不给你插嘴的机会：“还没完！我们要做个可达性检测系统。简单来说，就是判断——玩家从关卡 u 出发，能不能一路靠传送门跳到关卡 v？”。他打开了一张巨大的玩家需求表，继续说道：“毕竟现在的玩家可太会折腾了。你看，这批萌新想知道能不能偷偷传去高级区蹭经验，这群肝帝在研究哪些关卡属于同一个‘速刷联盟’。”他停顿了一下，“还有这几个家伙——专门研究怎么利用地图漏洞从新手村一路偷渡去打最终 BOSS。”

你沉默了两秒，试图用一句话终结这场需求轰炸，“明白，就是判断两个关卡在不在同一个连通分量里。”

策划眨了眨眼：“连通什么？反正你给我个布尔值就行，true 还是 false。” 说完，他露出职业策划特有的危险微笑，拍了拍你的肩膀：“放心，查询数量不多，也就十万条左右。例会前发我就行。”

第一反应：暴力建图？醒醒，你还想过试用期

你的第一反应很经典：既然 |nums[i] - nums[j]| <= maxDiff 就能连边，那我把所有满足条件的 (i, j) 对都找出来，建一张无向图，然后每次查询跑 BFS / DFS 判断是否可达，不就完事了？

你低头看向数据范围——n ≤ 10⁵ 个关卡，queries ≤ 10⁵ 次查询。好家伙，建图O(n²)，查询O(Q × N)，总复杂度10⁵ × 10⁵ = 10¹⁰——这个数字比你 Steam 库里所有游戏的累计时长换算成秒数还离谱。

“等等。” 你重新翻回需求文档。一行不起眼的信息，像 RPG 里的隐藏提示一样闪闪发光：

nums 已经按照非递减顺序排列。

这个条件绝对不是摆设。排序后的数组，就像一条从弱到强排列的副本长廊。传送门能不能开，只看相邻关卡的战力差。这就意味着这张图不是一张随意连接的蜘蛛网，而是一条被“战力断崖”切开的长链——所有连通块，都是一段一段连续的下标区间。

区域A              区域B          区域C
1--3--5--8   |   20--22   |   50--55
             ↑            ↑
          断崖          断崖

一个隐隐约约的念头浮了上来——这是利用有序性，把图论里的“连通问题”，降维成区间分组问题。

破局之道：给每个区域发一个标签

既然连通块都是连续区间，那直接从左到右扫描一遍，给每个关卡贴个“连通块标签号”不就行了？对于这种线性结构，一个 tags 数组直接搞定，根本不用上并查集。

操作简单到可以写在便利贴上，再贴到策划的冰美式杯子上：

初始时 tags[0] = 0，第一个节点属于第 0 号连通块。然后从 i = 1 开始往右扫描：

• 如果 nums[i] - nums[i-1] > maxDiff，说明这里有个断崖，tags[i] = tags[i-1] + 1——新开一个连通块，换张新标签。
• 否则，tags[i] = tags[i-1]——和前一个节点同一个连通块，沿用旧标签。

扫完一遍之后，同一连通块内的所有节点连通块标签相同，不同连通块的标签绝对不同。任意查询 [u, v] 就是 O(1) 的判断：tags[u] == tags[v]？相等就是一家人，传送随便开；不等就是中间隔了断崖，虚空乱流警告。

def pathExistenceQueries(n: int, nums: List[int], maxDiff: int, queries: List[List[int]]) -> List[bool]:
    tags = [0] * n
    for i in range(1, n):
        tags[i] = tags[i-1] + (nums[i] - nums[i-1] > maxDiff)
    return [tags[r] == tags[l] for l, r in queries]

没有嵌套循环，没有图遍历，没有递归。一次单调扫描 O(n)，每个查询 O(1)，总复杂度 O(n + q)。策划的十万条查询，在 tags 数组面前不过是把同一个 == 判断十万遍。

尾声：

你把结果打包发给策划，对面秒回：“这么快？你建好图了？”

你靠在椅背上打字：“没建图。你这张图里所有的传送门，本质上就是把战力相近的相邻关卡串成一条链。中间那些战力差太大的地方自然断开，形成几个连续区域。”

策划那边沉默了几秒，然后弹出来一行字：“所以……我画了一堆传送门的连线图，还让美术做了三天特效。结果你告诉我，它就是几个连续区间？”

“对。一条长廊，几道断崖，几张标签。同一张标签随便走，不同标签过不去。”

你顿了顿，决定补一刀，“你设计的不是传送网络，是一段一段的连续区间。图论是障眼法，数组才是本体。”

策划又沉默了。你几乎能想象他坐在对面盯着自己的设计稿，对自己前半生设计哲学产生了怀疑。

于是你决定说点什么，语气像在安慰又像在补刀：“下次如果想让传送门真的像一张网，记得把战力值打乱，别排好序。那样我就真要建图了————不过嘛，玩家体验也会从’丝滑传送’变成’随机跳伞’，你要不要考虑一下这个平衡性~”

对话框那头终于又亮了：“……你先别走，我在写新需求。”

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