代码共享

#include <bits/stdc++.h>
using namespace std;

int n, q, r[100005], x, y;
bool sm[100005]; // 特殊消息标记
int s[100005]; // 特殊消息编号
int idx[100005]; // 特殊消息在s中的下标
int dp[2005][2005]; // 特殊消息之间的最短距离
int lef[100005], rig[100005]; // 左右邻接特殊点

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++) {
        scanf("%d", r + i);
        if (r[i]) {
            sm[i] = sm[r[i]] = true;
        }
    }
    
    int t = 0;
    for (int i = 1; i <= n; i++) {
        if (sm[i]) {
            s[++t] = i;
            idx[i] = t;
        }
    }
    
    // 初始化dp数组
    const int INF = 1e9;
    for (int i = 1; i <= t; i++) {
        for (int j = 1; j <= i; j++) {
            dp[i][j] = INF;
        }
        dp[i][i] = 0;
    }
    
    // 方程推导
    for (int i = 1; i <= t; i++) {
        // 从 s[i] 出发
        for (int j = i; j >= 1; j--) {  // 注意：改成 j >= 1，但 j=1 时不处理
            // 从 s[j] 往前走一步到 s[j-1]
            if (j > 1) {
                int step1 = dp[i][j] + (s[j] - s[j-1]);
                dp[i][j-1] = min(dp[i][j-1], step1);
            }
            // 如果 s[j] 有引用，可以跳转
            if (r[s[j]] && idx[r[s[j]]]) {
                int k = idx[r[s[j]]];
                if (k < j) {  // 确保跳向更小的编号
                    dp[i][k] = min(dp[i][k], dp[i][j] + 1);
                }
            }
        }
    }
    
    // 处理所有消息的左右临界特殊点
    lef[0] = 0;
    for (int i = 1; i <= n; i++) {
        lef[i] = lef[i-1];
        if (sm[i]) lef[i] = i;
    }
    
    rig[n+1] = n+1;
    for (int i = n; i >= 1; i--) {
        rig[i] = rig[i+1];
        if (sm[i]) rig[i] = i;
    }
    
    // 开始询问
    while (q--) {
        scanf("%d%d", &x, &y);
        int le = lef[x], ri = rig[y];
        
        if (le < ri) {
            printf("%d\n", x - y);
        } else {
            // 确保 le 和 ri 都是有效的特殊消息
            if (le == 0) le = y;  // 如果没有左边特殊消息
            if (ri == n+1) ri = y; // 如果没有右边特殊消息
            
            int ans = (x - le) + (ri - y);
            if (le != ri) {
                ans += dp[idx[le]][idx[ri]];
            }
            printf("%d\n", ans);
        }
    }
    
    return 0;
}