A2682 [GESP-8.2603.T1] 消息查找

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;
    vector<int> r(n + 1, 0);
    for (int i = 1; i <= n; i++) cin >> r[i];

    // 只有引用了别的消息（r[i] > 0）的消息才能「跳」，这样的消息最多 1000 个
    vector<int> sp;
    for (int i = 1; i <= n; i++) {
        if (r[i] > 0) sp.push_back(i);
    }
    int m = (int)sp.size();

    // below[i]：sp 中最后一个 <= r[sp[i]] 的下标（即从 sp[i] 跳过去之后还能继续跳的位置）
    vector<int> below(m, -1);
    for (int i = 0; i < m; i++) {
        int lo = 0, hi = i - 1, best = -1;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (sp[mid] <= r[sp[i]]) {
                best = mid;
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        below[i] = best;
    }

    // best[i]：本次询问中，以 sp[i] 为第一个落点的连跳链最多能省下多少步
    vector<int> best(m + 1, 0);

    for (int k = 0; k < q; k++) {
        int x, y;
        cin >> x >> y;

        // 只有 sp[i] >= y 的消息才可能用来跳（跳过去就再也回不到 y 了）
        int lo = (int)(lower_bound(sp.begin(), sp.end(), y) - sp.begin());
        int hi = (int)(upper_bound(sp.begin(), sp.end(), x) - sp.begin()) - 1;

        int prefixMax = 0;
        for (int i = lo; i <= hi; i++) {
            int s = sp[i];
            int t = r[s];
            if (t >= y) {
                int j = below[i];
                // 跳一次省下 (s - t - 1) 步，之后还能接着往下连跳
                int f = (s - t - 1) + (j >= lo ? best[j] : 0);
                prefixMax = max(prefixMax, f);
            }
            best[i] = prefixMax;
        }

        int saved = (hi >= lo) ? best[hi] : 0;
        cout << (x - y - saved) << "\n";
    }
    return 0;
}