消息查找 题解

题目分析

我们有 $n$ 条消息，编号 $1 \sim n$，编号小的消息发送时间更早。每条消息 $i$ 可能引用一条更早的消息 $r_i(0\le r_i<i)$，若 $r_i = 0$ 表示没有引用。

当前查看位置可以在两种操作中任选其一：

1. 从 $i$ 移动到 $i-1$（左移一位）；
2. 如果消息 $i$ 有引用，则跳转到 $r_i$。

题目要求回答 $q$ 次询问：每次给定 $x,y(y<x)$，求从消息 $x$ 移动到消息 $y$ 的最少操作次数。

关键约束：至多只有 1000 条消息存在引用（即 $r_i>0$ 的 $i$ 不超过 1000 个）。

解题思路

1. 建立图模型

将所有消息看作点，操作看作有向边：

• 对于 $2 \le i \le n$，存在边 $i \to i-1$，边权为 $1$；
• 对于 $r_i>0$，存在边 $i \to r_i$，边权为 $1$。

所有边都由编号大的点指向编号小的点，形成一张有向无环图（DAG）。问题转化为：在这张图上求 $x$ 到 $y$ 的最短路径长度。

2. 利用引用边稀少的性质

虽然 $n$ 可达 $10^5$，但有引用的消息极少（$\le 1000$）。把与引用相关的消息称为关键点，具体包括：

• 所有发出引用的消息 $i$（即 $r_i>0$）；
• 所有被引用的消息 $r_i$。

因为这些点才涉及引用边（跳跃操作），其余点只能通过普通左移操作到达其他点。因此可以把图中的点分为“关键点”和“普通点”。关键点的总数记作 $cnt$，由于至多 1000 条引用消息，每条引用引入两个关键点，故 $cnt \le 2000$。

3. 预处理关键点之间最短路

将关键点按编号从小到大排序，记为 $p_1<p_2<\cdots <p_{cnt}$。在这些关键点之间有三种移动方式：

• 从 $p_j$ 一直左移到 $p_{j-1}$，距离为 $p_j - p_{j-1}$；
• 如果 $p_j$ 是一条引用消息，则可以一步跳到 $r_{p_j}$（也是一个关键点），距离为 $1$。

关键点之间的移动构成一张规模不超过 2000 的 DAG。我们可以用动态规划预处理出从第 $i$ 个关键点到第 $j$ 个关键点（$j \le i$）的最短距离 $d[i][j]$。

具体做法是：对每个 $i$，从 $j = i$ 开始向下更新：

• 用 $d[i][j]$ 更新 $d[i][j-1]$，加上左移距离 $p_j - p_{j-1}$；
• 若 $p_j$ 有引用，更新 $d[i][k]$，其中 $k$ 是 $r_{p_j}$ 在关键点序列中的下标，距离 $+1$。

由于所有边指向更小编号，按 $j$ 从大到小进行 DP 是正确的。时间复杂度 $O(cnt^2)$，即 $2000^2 = 4\times10^6$，完全可行。

4. 回答单次询问

对于询问 $(x, y)$，最短路径一定由三段组成：

1. 从 $x$ 向左走到某个关键点（进入关键点网络）；
2. 在关键点网络内部移动；
3. 从某个关键点向左走到 $y$（离开网络）。

为了最小化总步数，进入网络的关键点应选 $x$ 左边最近的关键点，记作 $pre[x]$；离开网络的关键点应选 $y$ 右边最近的关键点，记作 $suf[y]$。

• 如果 $pre[x]<suf[y]$，说明在 $y$ 和 $x$ 之间没有任何关键点，此时无法利用任何引用边，最优方案就是一路向左，答案为 $x - y$。
• 否则，答案为：

其中 $pos[p]$ 是关键点 $p$ 在 $p$ 数组中的下标。

单次询问只需 $O(1)$ 时间。

5. 预处理 $pre$ 和 $suf$ 数组

• $pre[i]$：编号 $\le i$ 的最大关键点。从左到右扫描：若当前 $i$ 是关键点，则 $pre[i] = i$；否则 $pre[i] = pre[i-1]$。
• $suf[i]$：编号 $\ge i$ 的最小关键点。从右到左扫描，类似处理。

时间复杂度均为 $O(n)$。

算法总结

1. 读入 $n, q$ 和引用数组 $r$，标记所有关键点；
2. 收集关键点并排序，建立位置到关键点下标的映射；
3. 用 $O(cnt^2)$ 的 DP 预处理关键点间最短路 $d$；
4. 预处理每个位置向左/向右最近的键点 $pre$ 和 $suf$；
5. 对每个询问 $O(1)$ 输出答案。

总时间复杂度 $O(n + cnt^2 + q)$，空间复杂度 $O(n + cnt^2)$，在 $cnt \le 2000$ 的约束下高效通过。

参考代码解释

cpp
复制
1#include <cstdio>
2#include <algorithm>
3using namespace std;
4
5const int N = 1e5 + 5;   // 最大消息数
6const int C = 2e3 + 5;   // 最大关键点数 (最多 2000)
7const int oo = 1e9;      // 无穷大
8
9int n, q;
10int r[N], mark[N], pos[N]; // r[i]: 引用关系; mark[i]: 是否为关键点; pos[i]: 关键点编号
11int p[C], cnt;            // p: 关键点编号数组; cnt: 关键点个数
12int d[C][C];              // d[i][j]: 关键点 p[i] 到 p[j] 的最短距离
13int pre[N], suf[N];       // 前驱后继最近关键点
14
15int main() {
16    scanf("%d%d", &n, &q);
17    for (int i = 1; i <= n; i++) {
18        scanf("%d", &r[i]);
19        if (r[i])
20            mark[i] = mark[r[i]] = 1; // 发出引用和被引用的消息都标记
21    }
22
23    // 收集所有关键点，按编号从小到大排列
24    for (int i = 1; i <= n; i++)
25        if (mark[i]) {
26            p[++cnt] = i;
27            pos[i] = cnt;     // 记录关键点在 p 数组中的下标
28        }
29
30    // 预处理关键点间最短路
31    for (int i = 1; i <= cnt; i++) {
32        for (int j = 1; j <= i; j++)
33            d[i][j] = oo;     // 初始化为无穷大
34        d[i][i] = 0;          // 自己到自己为 0
35        for (int j = i; j > 1; j--) {
36            // 向左走到上一个关键点
37            d[i][j - 1] = min(d[i][j - 1], d[i][j] + p[j] - p[j - 1]);
38            // 如果有引用，跳转到被引用的关键点
39            if (r[p[j]]) {
40                int k = pos[r[p[j]]];
41                d[i][k] = min(d[i][k], d[i][j] + 1);
42            }
43        }
44    }
45
46    // 预处理 pre 数组：i 左边最近的关键点
47    for (int i = 1; i <= n; i++) {
48        pre[i] = pre[i - 1];
49        if (mark[i])
50            pre[i] = i;
51    }
52
53    // 预处理 suf 数组：i 右边最近的关键点
54    suf[n + 1] = n + 1; // 哨兵
55    for (int i = n; i; i--) {
56        suf[i] = suf[i + 1];
57        if (mark[i])
58            suf[i] = i;
59    }
60
61    // 处理询问
62    while (q--) {
63        int x, y;
64        scanf("%d%d", &x, &y);
65        if (pre[x] < suf[y])       // 区间内无关键点
66            printf("%d\n", x - y);
67        else
68            printf("%d\n", x - pre[x] + d[pos[pre[x]]][pos[suf[y]]] + suf[y] - y);
69    }
70
71    return 0;
72}

代码细节说明

• 关键点收集：mark[i] = mark[r[i]] = 1 将发出引用和被引用的消息全部标记，构建完整的关键点集合。
• DP 最短路：从点 $p_i$ 出发，依次向左松弛。每次松弛只考虑相邻关键点之间的直接左移和可能的一步引用跳转，利用 DAG 的拓扑顺序正确计算出所有最短路。
• 询问处理：若 $pre[x]<suf[y]$，意味着 $y$ 和 $x$ 之间不存在任何关键点，只能直接左移；否则分段计算：走到左边的关键点 $\rightarrow$ 关键点间跳转 $\rightarrow$ 走到目标。

这样，我们利用“引用消息数量极少”的性质，将大规模图上的最短路问题压缩到小规模关键点图上，再结合预处理做到 $O(1)$ 回答询问，完美解决了本题。