简答题
适中
#24857
消息查找
消息查找


答案与解析
正确答案:<pre class="brush:cpp;toolbar:false;">#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; 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;
}</pre>
这道题暂未补解析。