GESP 题解库 / 8 级题解 / [GESP202603 八级] 消息查找 · 第 2 / 24 题
GESP202603 八级 · P15804 · 困难

消息查找

把"从 x 退到 y"反过来看成"从 y 走到 x",于是只需在有限个关键位置(两个询问端点 + 至多 2 × 1000 个引用端点)上扫一遍。

📨
n, q ≤ 10⁵
消息条数与询问次数
🔗
引用消息 ≤ 1000
至多有 1000 条 rᵢ > 0
⚡
O(q · k) ≈ 10⁸
每次询问只扫关键位置
🎯
反向最短路 + 关键位置压缩
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

小 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),那么接下来可以选择以下两种操作之一:

以上操作可以执行任意次(包括零次)。

小 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ₖ 所需的最少操作次数。

输入输出样例 #1

6 3
0 0 1 2 2 5
4 1
6 2
6 3

输出:

2
2
3

输入输出样例 #2

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,按编号从小到大扫一遍就是最短路。
再注意到"引用线最多 1000 条",绝大多数格子之间只能干走,于是把功夫全花在关键位置上就够了。

🔍 关键词提取

有向图最短路反向建图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)

需要解决的问题

02
思维导图
整理解题思路的全貌
🧭 反向走 + 只盯关键位置
🧠 问题转化
正向:i → i−1 或 i → rᵢ
反向:i−1 → i 与 rᵢ → i
"x 退到 y" 等价于 "y 走到 x"
反向边全部指向更大编号
✨ 关键位置
{y, x} ∪ 所有 rᵢ ∪ 所有 i
只有这些位置可能出现引用边
相邻关键位置之间只剩"干走"
每次询问只取 [y, x] 内的关键位置
✅ 为什么对
反向图是 DAG,升序即拓扑序
一次扫描就是最短路
d[p] = d[上一个] + (p − 上一个)
再与引用边 d[rᵢ] + 1 取 min
⚠️ 易错点
忘了把 y、x 也当成关键位置
引用起点 rᵢ < y 时不该使用这条边
每次询问都重排 O(n) 个位置(会超时)
询问可离线,但不必真离线
03
样例手算推导
样例 1 的三次询问,一次不漏地算一遍

🧮 样例 1:n = 6,r = [0, 0, 1, 2, 2, 5]

先列清楚引用线:3 → 1、4 → 2、5 → 2、6 → 5。注意 r₁ = r₂ = 0,这两条消息没有引用。

询问反向后的关键位置逐个关键位置的 d答案
4 1(x = 4, y = 1)1、2、3、4d(1) = 0,d(2) = 1,d(3) = 1,d(4) = 22
6 2(x = 6, y = 2)2、3、4、5、6d(2) = 0,d(3) = 1,d(4) = 1,d(5) = 1,d(6) = 22
6 3(x = 6, y = 3)3、4、5、6d(3) = 0,d(4) = 1,d(5) = 2,d(6) = 33
1
询问 (x = 4, y = 1):从 1 出发往 4 走

关键位置 = 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
询问 (x = 6, y = 2):注意 r₃ = 1 已被"甩在身后"

关键位置只取 [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
询问 (x = 6, y = 3):引用线全都够不到

关键位置: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 与一个"引用不一定更快"的例子

样例 2 的引用线是 4 → 1、5 → 3,5 次询问的答案依次是 1、2、2、2、1。其中 5 → 3 最省:一次引用就到位。

询问 (x, y)最优走法操作数
4 1直接按引用键:4 → 11
4 24 → 1(引用)→ 2(走一格)2
5 15 → 3(引用)→ 2 → 12
5 25 → 3(引用)→ 22
5 3直接按引用键:5 → 31
1
引用也可能"帮倒忙"

设想 n = 8,只有一条引用线 8 → 1

询问 (8, 1):答案 1(引用一次到底)

询问 (8, 2):若先引用到 1,再走到 2 要 1 步,共 2 步;但"从 8 一路走到 2"要 6 步

所以引用有时快、有时根本没参与

✅ 一律用 min 比较,不靠直觉

2
为什么"干走"这一项总在

相邻两个关键位置之间没有任何引用线的端点

所以在它们之间只能一格一格走

距离就是编号之差 p − p′

这也是"关键位置压缩"成立的根本原因

✅ 走路的代价可以整段一次算完

3
把两件事合起来

对每个关键位置 p,只有两种可能:

① 从上一个关键位置走过来:d[上一个] + (p − 上一个)

② 在 p 上按引用键:d[r_p] + 1(仅当 r_p ≥ y)

取两者的 min 就是 d[p]

整轮扫描 O(关键位置个数)

✅ 一次扫描定乾坤

⚠️
最容易踩的坑就在这里:引用线的起点 rᵢ 可能落在 y 的左边。此时反向图根本走不到 rᵢ(编号只能变大),所以这条引用边必须整条作废。
样例 1 的第二次询问 (6, 2) 就是活例子:3 → 1 的起点是 1,1 < y = 2,这条边不能用来更新 d(3),否则会算出一个偏小的错误答案。
04
解法对比
关键位置压缩 vs 每次询问暴力搜索

⚔️ 解法对比

🟢 反向最短路 + 关键位置压缩(推荐) 推荐

把询问反向后变成 DAG 上求最短路,每次只对 [y, x] 内的关键位置做一次升序扫描

  • 时间 O(n + q · k),k ≤ 1000
  • 约 2 × 10⁸ 次简单操作
  • 代码约 60 行
  • 在线处理,来一条答一条
💡
为什么关键位置只要这么几个?
反向图里的边只有两类:走路 i − 1 → i 与引用 rᵢ → i。
如果某个位置既不是询问端点、又不挨着任何引用线,那它只能"被动经过",对它的距离无非是前一个关键位置加一段差值——不必单独维护。

🟠 每次询问从 x 正向 BFS

把两种操作当成有向边,每次询问跑一次 BFS

  • 单次 O(n),正确性最好理解
  • q 次合计 O(q · n) = 10¹⁰
  • 代码约 30 行
  • 40% 部分分(n, q ≤ 2000)够用
⚠️
它慢在哪:相邻两次询问的信息完全不复用,
而本题的引用线只有 1000 条,真正"值得搜索"的地方极少,99% 的格子之间都只是走路。
把搜索范围压到关键位置上,单次询问从 10⁵ 降到 10³,整整快 100 倍。

📈 性能对比

方案复杂度代码量
反向最短路 + 关键位置O(n + q · k) ≈ 2 × 10⁸约 60 行 ✅ 推荐
每次询问正向 BFSO(q · n) = 10¹⁰约 30 行 ❌ 超时
对每个起点预处理全部答案O(n²) = 10¹⁰约 40 行 ❌ 超时且爆空间
05
算法流程图
一次询问的处理流程(反向扫描)
开始读入 n、q 与数组 r,只保留 rᵢ > 0 的引用线逐条处理询问 (x, y)取关键位置:y、x,以及所有落在 [y, x] 内的 rᵢ 与 i把关键位置按编号升序排好(两张有序表归并,O(k))d[y] = 0,从 y 开始扫走到下一个关键位置 p:先记 d[p] = d[上一个] + (p − 上一个)p 上挂着可用的引用线 r_p 吗?有 ✓d[p] = min(d[p], d[r_p] + 1)没有 ✗d[p] 保持走路值还有关键位置没扫完吗?输出 d[x],再处理下一条询问取下一个关键位置继续扫描
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

📨 消息查找器(反向扫描 + 关键位置)

第一行输入 n q,第二行输入 n 个引用编号 rᵢ(0 表示没有引用),随后 q 行每行输入 x y(y < x)。程序会对每次询问列出关键位置与每个位置的最少操作数。演示规模取 n ≤ 12、q ≤ 8。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码(反向最短路 + 关键位置归并)

#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 混合运算就容易溢出。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
6 3
0 0 1 2 2 5
4 1
6 2
6 3
2 / 2 / 3题面样例 1:注意 (6,2) 时引用线 3 → 1 越界作废
5 5
0 0 0 1 3
4 1
4 2
5 1
5 2
5 3
1 / 2 / 2 / 2 / 1题面样例 2:一次引用直达就是最优
3 1
0 0 0
3 1
2完全没有引用线:只能一格一格退,答案 = x − y
4 2
0 0 1 1
4 1
4 3
1 / 1引用直达(4 → 1)与"走一格"各占一次询问
5 1
0 0 0 1 3
5 2
2引用 + 走一格的组合,5 → 3(引用)→ 2
6 2
0 0 0 1 3 0
6 1
6 5
3 / 1同一张数据两次询问,答案差别很大
5 1
0 0 0 0 0
5 1
4y 与 x 相距最远且无引用,答案 = 4
100000 100000(引用线 1000 条)运行验证最大规模,考察 O(q · k) 是否跑得动
✅
自查清单:① 关键位置包含 y 和 x 吗?② rᵢ ≥ y 判了吗?③ 扫描是升序的吗?④ 有没有把单次询问搞成 O(n)?

🚨 易错点清单

⚠️
引用线越界:rᵢ < y 的引用边整条不可用,这是最常见也最致命的错误(答案会偏小)。
⚠️
关键位置漏掉端点:必须显式把 y 与 x 加进关键位置集合。
⚠️
每次询问清空 O(n) 的数组:那就把优化白费了,用时间戳(query id)区分即可。
⚠️
以为"引用一定更快":引用可能把人带到很左边,反而多走很多步,一律取 min。
⚠️
把反向边写反:正向是 i → i − 1 与 i → rᵢ,反向是 i − 1 → i 与 rᵢ → i。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n + q · k)
空间复杂度
O(n + k)
每次询问
O(k),k ≤ 1000
总运算量
约 2 × 10⁸

时间怎么算的?

空间都用在哪?

数组 r、dval、seen 各占 O(n),关键位置数组 ks 占 O(k)。两张有序表 byI、byR 也各只有 k 个元素——整个算法几乎不占额外空间。

✅ 2 × 10⁸ 次简单整数操作,配上快读即可稳定通过 1 秒时限。把"每次询问一趟 BFS"压成"只扫关键位置",这就是本题的全部功夫。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 「反向建图 + 关键位置压缩」通用骨架
// 适用场景:图上只有少数"特殊边",其余位置只能顺次移动

// 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),压缩法就永远成立——这就是这个套路真正的坚固之处。)