题解：P13522 [KOI 2025 #2] 机器人

Charged_Charge · 2026-07-22 22:12:02 · 题解

思路：

预处理一个跳板最终会使机器人到哪一个跳板上去，并同时维护这一段的时间。然后对于每一个询问，用二分确认机器人最初的跳板区间。

• 若该机器人在第一块跳板之前，则它会一直向左走。
• 若该机器人走到最近的跳板所需的时间大于它的行动时间，则直接得出位置 s_i - t_i。
• 否则倍增得出该机器人最后会停留的跳板区间。模拟维护它的最终位置。

AC 代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 3e5 + 10;
int n, q;
ll qx[N], p[N], f[23][N], s[23][N];
int main() {
    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> qx[i] >> p[i];
    }

    for (int i = 1; i < n; i++) {
        ll pn = p[i];
        while (pn + qx[i] < qx[i + 1]) {
            s[0][i] += pn + 1;
            pn *= 2;
        }

        int x = upper_bound(qx + i + 1, qx + 1 + n, pn + qx[i]) - qx - 1;
        f[0][i] = x;
        s[0][i] += qx[i] + pn - qx[x] + 1;
    }

    s[0][n] = 1e18;
    f[0][n] = n;
    for (int j = 1; j <= 21; j++) {
        for (int i = 1; i <= n; i++) {
            s[j][i] = min(s[j - 1][f[j - 1][i]] + s[j - 1][i], (ll)1e18);
            f[j][i] = f[j - 1][f[j - 1][i]];
        }
    }

    cin >> q;

    while (q--) {
        ll qs, qt;
        cin >> qs >> qt;
        int x = upper_bound(qx + 1, qx + 1 + n, qs) - qx - 1;

        if (x == 0) {
            cout << qs - qt << '\n';
            continue;
        }

        if (qs - qx[x] >= qt) {
            cout << qs - qt << '\n';
            continue;
        }

        qt -= qs - qx[x];

        for (int i = 21; i >= 0; i--) {
            if (s[i][x] <= qt) {
                qt -= s[i][x];
                x = f[i][x];
            }
        }

        qs = qx[x];
        ll pn = p[x];

        while (qt) {
            if (qt < pn + 1) {
                qs += pn;
                qt--;
                qs -= qt;
                break;
            }

            qt -= pn + 1;
            pn *= 2;
        }

        cout << qs << '\n';
    }

    return 0;
}