A20935. 消息查找
填空题
困难
知识点
题目描述
消息查找
题目描述
小A的消息记录中有n条消息，依次以1,2,...,n编号。编号小的消息发送时间早于编号大的消息。一条消息可以引用一条编号小于它的消息，也可以不引用消息。小A注意到消息记录里有引用的消息数量不会非常多。消息记录的一个例子是:
- 【消息 1】小A：有人做了今天的第一题吗？
- 【消息 2】小A：我第一题 WA 了，可能是什么原因？
- 【消息 3：引用消息 1】小B：我我我
- 【消息 4：引用消息 2】小C：我也 WA 了
- 【消息 5：引用消息 2】小B：是不是没开 long long ？
- 【消息 6：引用消息 5】小A：改了就AC 了，太厉害了！
对于消息i(1≤i≤n)，小A以ri标记消息是否有引用，以及所引用的消息编号。如果ri>0,则消息i为引用了消息ri;如果ri=0，则消息i没有引用消息。
消息记录里有非常多条消息。为了快速查找所需要的消息，小A准备实现一个简单的消息查找工具。消息查找工具任意时刻只能定位恰好一条消息，如果当前位于消息i(1<i≤n)，那么接下来可以选择以下两种操作之一:
- 定位到消息i-1;
- 如果消息i引用了消息ri，定位到消息ri。
以上操作可以执行任意次(包括零次)。
小A有q次询问。在第k(1≤k≤q)次询问中，小A给出消息编号xk,yk(yk≤xk)。小A想知道，如果当前消息查找工具位于xk，至少需要多少次操作才能定位到消息yk。
输入格式
第一行，两个正整数n,q，分别表示消息条数与询问次数。
第二行，n个非负整数r1,r2,...,rn，表示消息的引用关系，具体含义见题目描述。
接下来q行中的第k行(1≤k≤q)包含两个正整数xk,yk，表示一次询问。
保证至多只有1000条引用消息。
输出格式
输出q行，每行一个整数，表示将界面从消息xk切换到消息yk所需的最少操作次数。
样例
输入样例 1
6 3
0 0 1 2 2 5
4 1
6 2
6 3 输出样例 1
2
2
3输入样例 2
5 5
0 0 0 1 3
4 1
4 2
5 1
5 2
5 3 输出样例 2
1
2
2
2
1数据范围
对于40%的测试点，保证1≤n≤2000，1≤q≤2000。
对于所有测试点，保证1≤n≤105,1≤q≤105,0≤ri<i,1≤yk<xk≤n，保证至多有1000条引用消息。
参考答案
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
const int C = 2e3 + 5;
const int oo = 1e9;
int n, q;
int r[N], mark[N], pos[N];
int p[C], cnt;
int d[C][C];
int pre[N], suf[N];
int main() {
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++) {
scanf("%d", &r[i]);
if (r[i])
mark[i] = mark[r[i]] = 1;
}
for (int i = 1; i <= n; i++)
if (mark[i]) {
p[++cnt] = i;
pos[i] = cnt;
}
for (int i = 1; i <= cnt; i++) {
for (int j = 1; j <= i; j++)
d[i][j] = oo;
d[i][i] = 0;
for (int j = i; j > 1; j--) {
d[i][j - 1] = min(d[i][j - 1], d[i][j] + p[j] - p[j - 1]);
if (r[p[j]]) {
int k = pos[r[p[j]]];
d[i][k] = min(d[i][k], d[i][j] + 1);
}
}
}
for (int i = 1; i <= n; i++) {
pre[i] = pre[i - 1];
if (mark[i])
pre[i] = i;
}
suf[n + 1] = n + 1;
for (int i = n; i >= 1; i--) {
suf[i] = suf[i + 1];
if (mark[i])
suf[i] = i;
}
while (q--) {
int x, y;
scanf("%d%d", &x, &y);
if (pre[x] < suf[y])
printf("%d\n", x - y);
else
printf("%d\n", x - pre[x] + d[pos[pre[x]]][pos[suf[y]]] + suf[y] - y);
}
return 0;
}
上一题
下一题