把"从 x 退到 y"反过来看成"从 y 走到 x",于是只需在有限个关键位置(两个询问端点 + 至多 2 × 1000 个引用端点)上扫一遍。
小 A 的消息记录中有 n 条消息,依次以 1, 2, …, n 编号。编号小的消息发送时间早于编号大的消息。
一条消息可以引用一条编号小于它的消息,也可以不引用消息。小 A 注意到消息记录里有引用的消息数量不会非常多。消息记录的一个例子是:
对于消息 i(1 ≤ i ≤ n),小 A 以 rᵢ 标记消息 i 是否有引用,以及所引用的消息编号。如果 rᵢ > 0,则消息 i 为引用了消息 rᵢ;如果 rᵢ = 0,则消息 i 没有引用消息。
消息记录里有非常多条消息。为了快速查找所需要的消息,小 A 准备实现一个简单的消息查找工具。消息查找工具任意时刻只能定位恰好一条消息,如果当前位于消息 i(1 < i ≤ n),那么接下来可以选择以下两种操作之一:
i − 1;i 引用了消息 rᵢ,定位到消息 rᵢ。以上操作可以执行任意次(包括零次)。
小 A 有 q 次询问。在第 k(1 ≤ k ≤ q)次询问中,小 A 给出消息编号 xₖ, yₖ(yₖ < xₖ)。小 A 想知道,如果当前消息查找工具位于 xₖ,至少需要多少次操作才能定位到消息 yₖ。
第一行,两个正整数 n, q,分别表示消息条数与询问次数。
第二行,n 个非负整数 r₁, r₂, …, rₙ,表示消息的引用关系,具体含义见题目描述。
接下来 q 行中的第 k 行(1 ≤ k ≤ q)包含两个正整数 xₖ, yₖ,表示一次询问。
保证至多只有 1000 条引用消息。
输出 q 行,每行一个整数,表示将界面从消息 xₖ 切换到消息 yₖ 所需的最少操作次数。
6 3 0 0 1 2 2 5 4 1 6 2 6 3
输出:
2 2 3
5 5 0 0 0 1 3 4 1 4 2 5 1 5 2 5 3
输出:
1 2 2 2 1
对于 40% 的测试点,保证 1 ≤ n ≤ 2000,1 ≤ q ≤ 2000。
对于所有测试点,保证 1 ≤ n ≤ 10⁵,1 ≤ q ≤ 10⁵,0 ≤ rᵢ < i,1 ≤ yₖ < xₖ ≤ n,保证至多有 1000 条引用消息。
1 … n 想成一排格子,你站在格子 x,只能往左挪一格(i → i − 1),或者顺着引用线跳(i → rᵢ,而引用线总是连向更小的编号)。y(y < x)上?x 做一次 BFS,O(q · n) = 10¹⁰,凉。x 退到 y"等价于"从 y 走到 x",此时可走的边变成 i − 1 → i(走一格)和 rᵢ → i(顺引用线)。这两种边都让编号变大,所以反向图是一张 DAG,按编号从小到大扫一遍就是最短路。有向图最短路反向建图DAG 拓扑序关键位置压缩离线批量询问
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n、q;第二行 n 个 rᵢ;随后 q 行每行 x、y |
| 输出 | 每次询问一行答案 |
| 数据范围 | 1 ≤ n, q ≤ 10⁵ |
| 引用关系 | 0 ≤ rᵢ < i,至多 1000 条 rᵢ > 0 |
| 询问 | 1 ≤ yₖ < xₖ ≤ n(只往小号方向查) |
| 操作 | i → i − 1(代价 1);i → rᵢ(代价 1,仅当 rᵢ > 0) |
q ≤ 10⁵ 次询问 × 每次 O(n) = 10⁵,一共 10¹⁰ 步i → i − 1 与 i → rᵢ,反过来就是 i − 1 → i 与 rᵢ → i,每条边都从小编号指向大编号,于是图是无环的(DAG),编号升序就是天然的拓扑序p − p′O(q · k)?关键位置的个数是 O(k + 2)(k ≤ 1000 条引用),每次询问只在这几个位置上扫描,总共约 2 × 10⁸ 次简单操作先列清楚引用线:3 → 1、4 → 2、5 → 2、6 → 5。注意 r₁ = r₂ = 0,这两条消息没有引用。
| 询问 | 反向后的关键位置 | 逐个关键位置的 d | 答案 |
|---|---|---|---|
| 4 1(x = 4, y = 1) | 1、2、3、4 | d(1) = 0,d(2) = 1,d(3) = 1,d(4) = 2 | 2 |
| 6 2(x = 6, y = 2) | 2、3、4、5、6 | d(2) = 0,d(3) = 1,d(4) = 1,d(5) = 1,d(6) = 2 | 2 |
| 6 3(x = 6, y = 3) | 3、4、5、6 | d(3) = 0,d(4) = 1,d(5) = 2,d(6) = 3 | 3 |
关键位置 = 1、2、3、4(其中 3、4 挂着引用线)
d(1) = 0(起点)
d(2) = d(1) + (2 − 1) = 1(纯走)
d(3):先走 d(2) + 1 = 2;再看引用线 3 → 1,候选 d(1) + 1 = 1 → 取 min = 1
d(4):先走 d(3) + 1 = 2;再看引用线 4 → 2,候选 d(2) + 1 = 2 → 保持 2
✅ d(4) = 2
关键位置只取 [2, 6] 内的:2、3、4、5、6
d(2) = 0
d(3) = 1(引用线 3 → 1 的起点 1 < 2,越界,不能用)
d(4):走 = 2;引用 4 → 2 给 d(2) + 1 = 1 → 取 1
d(5):走 = 2;引用 5 → 2 给 d(2) + 1 = 1 → 取 1
d(6):走 = 2;引用 6 → 5 给 d(5) + 1 = 2 → 保持 2
✅ d(6) = 2
关键位置:3、4、5、6
d(3) = 0
d(4):r₄ = 2 < 3,引用不可用 → d(4) = d(3) + 1 = 1
d(5):r₅ = 2 < 3,不可用 → d(5) = 2
d(6):r₆ = 5 ≥ 3,候选 d(5) + 1 = 3;走路也是 d(5) + 1 = 3 → d(6) = 3
✅ d(6) = 3
x 出发时,你完全无法预测"该不该提前按引用键"——要先退几步才能引用到合适的消息,这需要搜索。y 出发,引用线 rᵢ → i 与走路 i − 1 → i 都指向更大的编号,于是"先算小的、再拿小的推大的"就是天然正确的顺序——这就把搜索题变成了简单的递推题。样例 2 的引用线是 4 → 1、5 → 3,5 次询问的答案依次是 1、2、2、2、1。其中 5 → 3 最省:一次引用就到位。
| 询问 (x, y) | 最优走法 | 操作数 |
|---|---|---|
| 4 1 | 直接按引用键:4 → 1 | 1 |
| 4 2 | 4 → 1(引用)→ 2(走一格) | 2 |
| 5 1 | 5 → 3(引用)→ 2 → 1 | 2 |
| 5 2 | 5 → 3(引用)→ 2 | 2 |
| 5 3 | 直接按引用键:5 → 3 | 1 |
设想 n = 8,只有一条引用线 8 → 1
询问 (8, 1):答案 1(引用一次到底)
询问 (8, 2):若先引用到 1,再走到 2 要 1 步,共 2 步;但"从 8 一路走到 2"要 6 步
所以引用有时快、有时根本没参与
✅ 一律用 min 比较,不靠直觉
相邻两个关键位置之间没有任何引用线的端点
所以在它们之间只能一格一格走
距离就是编号之差 p − p′
这也是"关键位置压缩"成立的根本原因
✅ 走路的代价可以整段一次算完
对每个关键位置 p,只有两种可能:
① 从上一个关键位置走过来:d[上一个] + (p − 上一个)
② 在 p 上按引用键:d[r_p] + 1(仅当 r_p ≥ y)
取两者的 min 就是 d[p]
整轮扫描 O(关键位置个数)
✅ 一次扫描定乾坤
rᵢ 可能落在 y 的左边。此时反向图根本走不到 rᵢ(编号只能变大),所以这条引用边必须整条作废。(6, 2) 就是活例子:3 → 1 的起点是 1,1 < y = 2,这条边不能用来更新 d(3),否则会算出一个偏小的错误答案。把询问反向后变成 DAG 上求最短路,每次只对 [y, x] 内的关键位置做一次升序扫描
i − 1 → i 与引用 rᵢ → i。把两种操作当成有向边,每次询问跑一次 BFS
10⁵ 降到 10³,整整快 100 倍。| 方案 | 复杂度 | 代码量 |
|---|---|---|
| 反向最短路 + 关键位置 | O(n + q · k) ≈ 2 × 10⁸ | 约 60 行 ✅ 推荐 |
| 每次询问正向 BFS | O(q · n) = 10¹⁰ | 约 30 行 ❌ 超时 |
| 对每个起点预处理全部答案 | O(n²) = 10¹⁰ | 约 40 行 ❌ 超时且爆空间 |
第一行输入 n q,第二行输入 n 个引用编号 rᵢ(0 表示没有引用),随后 q 行每行输入 x y(y < x)。程序会对每次询问列出关键位置与每个位置的最少操作数。演示规模取 n ≤ 12、q ≤ 8。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll INF = (ll)4e18; int n, q; int r[100005]; vector<int> byI; // 所有 rᵢ > 0 的 i(读入时天然升序) vector<int> byR; // 所有 rᵢ 的值(排序后升序) ll dval[100005]; // d 值 int seen[100005]; // 时间戳:避免每次询问都把数组清空 int qid = 0; static int ks[4005]; // 本次询问用到的关键位置 inline ll getD(int p) { return seen[p] == qid ? dval[p] : INF; } inline void setD(int p, ll v) { seen[p] = qid; dval[p] = v; } int main() { scanf("%d %d", &n, &q); for (int i = 1; i <= n; i++) { scanf("%d", &r[i]); if (r[i] > 0) { byI.push_back(i); byR.push_back(r[i]); } } sort(byR.begin(), byR.end()); while (q--) { int x, y; scanf("%d %d", &x, &y); ++qid; // ---------- 1) 用两张有序表归并出 [y, x] 内的关键位置,O(k) ---------- int kc = 0; ks[kc++] = y; // 所有关键位置都 ≥ y,y 一定最小 int a = lower_bound(byR.begin(), byR.end(), y) - byR.begin(); int b = lower_bound(byI.begin(), byI.end(), y) - byI.begin(); while (true) { int v = INT_MAX; if (a < (int)byR.size() && byR[a] <= x) v = min(v, byR[a]); if (b < (int)byI.size() && byI[b] <= x) v = min(v, byI[b]); if (v == INT_MAX) break; if (ks[kc - 1] != v) ks[kc++] = v; // 去重后追加 if (a < (int)byR.size() && byR[a] == v) a++; if (b < (int)byI.size() && byI[b] == v) b++; } if (ks[kc - 1] != x) ks[kc++] = x; // 所有关键位置都 ≤ x,x 一定最大 // ---------- 2) 按编号升序扫描(反向图是 DAG) ---------- setD(y, 0); ll cur = 0; for (int t = 1; t < kc; t++) { int p = ks[t]; cur += (p - ks[t - 1]); // 从上一个关键位置一路走来 if (r[p] > 0 && r[p] >= y) { // 位置 p 上有一条第起点可达的引用线 ll cand = getD(r[p]) + 1; if (cand < cur) cur = cand; } setD(p, cur); } printf("%lld\n", cur); // cur 就是 d[x] } return 0; }
y 与 x 塞进关键位置,否则起终点会被跳过;② 归并时两张表都已经有序(byI 读入即升序,byR 排一次序),所以单次询问只需 O(k);③ 引用边可用性判断要写成 r[p] ≥ y,起点落在 y 左边的引用线一律作废;④ 距离用时间戳数组代替"每次清空",把单次询问的额外开销从 O(n) 压到 O(1)。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
ks[kc++] = y; … if (ks[kc-1] != x) ks[kc++] = x; | 补上两个端点 | y 是最小、x 是最大的关键位置,一前一后拼在两头 |
lower_bound(byR.begin(), byR.end(), y) | 定位落脚点 | 两张表都是升序,二分出第一个 ≥ y 的位置即可 |
if (a < size && byR[a] <= x) v = min(v, byR[a]); | 归并两表 | 等价于一次"双路归并排序",天然去重又保序 |
cur += (p - ks[t-1]); | 纯走路代价 | 相邻关键位置之间没有任何引用端点,只能一格一格挪 |
if (r[p] > 0 && r[p] >= y) | 引用边可用性 | r[p] < y 表示这条边在可达范围之外 |
seen[p] == qid | 免清空技巧 | 用时间戳区分"本轮写过"和"上轮残留",O(1) 复位 |
y、x 当关键位置,答案直接错;② 不判断 r[p] ≥ y,用到了越界的引用线,答案偏小;③ 每次询问都开一个长度为 n 的数组并清零,额外开销变成 O(q · n) = 10¹⁰,白优化;④ 用 int 存答案——虽然本题答案不超过 n,但公式 d[r] + 1 若与 INF 混合运算就容易溢出。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
6 3 | 2 / 2 / 3 | 题面样例 1:注意 (6,2) 时引用线 3 → 1 越界作废 |
5 5 | 1 / 2 / 2 / 2 / 1 | 题面样例 2:一次引用直达就是最优 |
3 1 | 2 | 完全没有引用线:只能一格一格退,答案 = x − y |
4 2 | 1 / 1 | 引用直达(4 → 1)与"走一格"各占一次询问 |
5 1 | 2 | 引用 + 走一格的组合,5 → 3(引用)→ 2 |
6 2 | 3 / 1 | 同一张数据两次询问,答案差别很大 |
5 1 | 4 | y 与 x 相距最远且无引用,答案 = 4 |
100000 100000(引用线 1000 条) | 运行验证 | 最大规模,考察 O(q · k) 是否跑得动 |
rᵢ ≥ y 判了吗?③ 扫描是升序的吗?④ 有没有把单次询问搞成 O(n)?rᵢ < y 的引用边整条不可用,这是最常见也最致命的错误(答案会偏小)。y 与 x 加进关键位置集合。i → i − 1 与 i → rᵢ,反向是 i − 1 → i 与 rᵢ → i。O(n),把 1000 个引用值排一次序 O(k log k)O(log k) + 归并 O(k) + 扫描 O(k)O(n + q · k),把 q = k = 10⁵ / 10³ 代入约 2 × 10⁸2k + 2 ≈ 2002数组 r、dval、seen 各占 O(n),关键位置数组 ks 占 O(k)。两张有序表 byI、byR 也各只有 k 个元素——整个算法几乎不占额外空间。
✅ 2 × 10⁸ 次简单整数操作,配上快读即可稳定通过 1 秒时限。把"每次询问一趟 BFS"压成"只扫关键位置",这就是本题的全部功夫。
// 「反向建图 + 关键位置压缩」通用骨架 // 适用场景:图上只有少数"特殊边",其余位置只能顺次移动 // 1) 反向:把"从 x 退到 y"变成"从 y 走到 x" // 正向边 i -> i-1 / i -> r[i] => 反向边 i-1 -> i / r[i] -> i // 所有反向边的端点编号都严格变大 => DAG => 升序扫描即最短路 // 2) 压缩:只保留"可能改变答案"的位置 // 关键位置 = {y, x} ∪ {所有特殊边的两个端点},并且裁剪到 [y, x] // 相邻关键位置之间没有任何特殊边 => 代价就是编号之差 // 3) 扫描:一次线性递推 // d[y] = 0 // for (关键位置 p 升序, p > y): // d[p] = d[上一个关键位置] + (p - 上一个关键位置) // 纯走 // if (存在特殊边 r[p] -> p 且 r[p] >= y) // d[p] = min(d[p], d[r[p]] + 1) // 用特殊边 // 答案 = d[x] // 4) 免清空:用 query id + 时间戳数组,把单次询问的初始化开销降到 O(1) // getD(p): return seen[p] == qid ? dval[p] : INF;
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 反向建图 | 把"往回退"翻译成"往前走",边方向统一 | 所有"只能减小下标"的移动题(跳格子、翻页、退版本) |
| 关键位置压缩 | 只有特殊边的端点值得单独维护 | 区间内只有少数"跳跃点"的最短路 / 区间查询 |
| DAG 上的最短路 | 按拓扑序一次扫描,不需要堆 | 所有边方向单调的有向图(含 DP 建模题) |
| 时间戳免清空 | 用操作编号区分本轮/上轮数据 | 多组询问共用一个大数组的所有场景 |
rᵢ 的同时还能顺便再往前一格"(即 i → rᵢ 与 i → rᵢ − 1 都算一次操作),上面的做法还成立吗?(提示:把新边加进"关键位置 + 松弛规则"里即可,因为新边的起点 rᵢ − 1 仍然是特殊边的端点。只要"特殊边的端点数"仍是 O(k),压缩法就永远成立——这就是这个套路真正的坚固之处。)