概要

一列に並んだ選手たちの間で、ルールに従ってボールをパスしていくシミュレーション問題です。各ボールについて、最終的にいずれかの選手にキャッチされるか、あるいはこれ以上パスできなくなって終了するかを判定します。

パスの移動先が一意に決まること（Functional Graph）に着目し、逆方向の BFS（幅優先探索）とダブリング（Doubling）を組み合わせることで、各クエリを高速に処理します。

---

考察

1. パス先の決定（一意性）

選手 \(i\) がパスをする相手は、ルールより「自分を除いて最も番号の小さい選手」です。 選手 \(i\) のパス範囲 \([L_i, R_i]\) において、自分自身を除いたときの最小の番号 nxt[i] は以下のように一意に決定されます。

• \(L_i = R_i = i\) のとき： 自分以外の選手が範囲内にいないため、パスできません（最終保持者となります）。
• \(L_i < i\) のとき： 自分より左側（番号が小さい方）に選手が存在します。範囲内の最小値は必ず \(L_i\) になります。したがって、パス先は \(L_i\) です。
• \(L_i = i\) かつ \(R_i > i\) のとき： 自分より左側には選手がおらず、右側にのみ存在します。自分を除いた最小の番号は \(i + 1\) になります。したがって、パス先は \(i + 1\) です。

このように、各選手からの遷移先は常に1つに決まります。これは、選手たちのパス関係が出次数が1の有向グラフ（Functional Graph）をなしていることを意味します。

2. ダミー頂点の導入と最終保持者の事前計算

パスができない選手に到達した場合、その選手が「最終保持者」となります。 実装をシンプルにするために、パスができない選手からの遷移先としてダミー選手 \(N+1\) を用意します。ダミー選手 \(N+1\) のキャッチ力は \(-\infty\) とし、絶対にボールをキャッチしないようにします。

ボールがキャッチされずに進み続けた場合、最終的にどの「パス不可の選手」にたどり着くかは、開始位置 \(T_j\) のみによって一意に決まります。 そこで、ダミー頂点 \(N+1\) から逆辺をたどる BFS を行うことで、すべての選手 \(u\) について、「キャッチを無視して進んだときに最終的に到達するパス不可の選手」 last[u] を \(O(N)\) で事前計算しておくことができます。

3. キャッチされるかどうかの判定（ダブリング）

ボールのスピードは1回のパスごとに \(1\) 減少します。 選手 \(curr\) からスタートして \(s\) 歩進んだとき、その選手を \(v\) とすると、キャッチされる条件は \(W - s \le D_v\)、すなわち \(W \le D_v + s\) となります。

クエリごとに1歩ずつシミュレーションすると、最大で \(10^9\) 歩かかるため実行時間制限（TLE）に間に合いません。 そこで、ダブリングを用いて「\(2^p\) 歩進む間にキャッチされるか？」を高速に判定します。

---

アルゴリズム

ダブリングテーブルの構築

以下の2つのテーブルを定義します。

• to_dbl[p][i]：選手 \(i\) から \(2^p\) 歩進んだ先の選手。
• max_val[p][i]：選手 \(i\) から \(2^p\) 歩進む間の \(\max (D_{path[s]} + s)\) の値。

遷移式は以下のようになります。

\[ \text{to\_dbl}[p][i] = \text{to\_dbl}[p-1][\text{to\_dbl}[p-1][i]] \]

\[ \text{max\_val}[p][i] = \max \left( \text{max\_val}[p-1][i], \ \text{max\_val}[p-1][\text{to\_dbl}[p-1][i]] + 2^{p-1} \right) \]

※ 後半の \(2^{p-1}\) 歩では、スタートからのステップ数が \(2^{p-1}\) だけオフセット（加算）されるため、後半部分の max_val に \(2^{p-1}\) を足して重ね合わせます。

クエリの処理

各ボール \((T, W)\) について、現在地 curr = T、これまでに進んだ歩数 dist = 0 とします。 \(p = 29\) から \(0\) まで降順にループを回します。

• もし \(W \le \text{max\_val}[p][curr] + \text{dist}\) ならば、この \(2^p\) 歩の間にキャッチされてしまうため、進みません。
• そうでなければ、この \(2^p\) 歩の間はキャッチされないため、安全に進めることができます。dist += 2^p, curr = to_dbl[p][curr] と更新します。

ループ終了後、curr は「キャッチされずに進める限界の直前」にいます。 最後に、次の1歩（すなわち現在の curr）でキャッチされるかを判定します。

• \(W \le D_{curr} + \text{dist}\) ならば、この位置でキャッチされるため、答えは -1 です。
• そうでなければ、一度もキャッチされずにパス不可の選手まで到達できるため、答えは事前に求めた last[T] となります。

---

計算量

• 時間計算量: \(O((N + M) \log (\max W))\)

  • 遷移先の決定と逆辺 BFS: \(O(N)\)
  • ダブリングテーブルの構築: \(O(N \log (\max W))\)
  • 各クエリの処理: \(O(\log (\max W))\)
  • \(N, M \le 2 \times 10^5\), \(\max W \le 10^9\)（\(\log_2(10^9) \approx 30\)）であるため、実行時間制限に十分間に合います。

• 空間計算量: \(O(N \log (\max W))\)

  • ダブリングテーブルのサイズが支配的です。

---

実装のポイント

• オーバーフローの防止: キャッチ力の判定において D[i] + dist や max_val の値が大きくなるため、計算には long long 型（64ビット整数）を使用する必要があります。

• ダミー頂点の設定: ダミー頂点 \(N+1\) のキャッチ力は、絶対にキャッチされないように十分に小さな値（-10^15 など）に設定します。

• ダブリングのサイズ: \(W_j \le 10^9\) であるため、ダブリングの段階数 \(P\) は \(2^{30} > 10^9\) となる \(P = 30\) で十分です。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

const long long INF = 1000000000000000LL; // 10^15

int main() {
    // 高速な入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    if (!(cin >> N >> M)) return 0;

    vector<long long> D(N + 2);
    vector<int> L(N + 1), R(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> D[i] >> L[i] >> R[i];
    }
    // ダミー頂点 N+1 のキャッチ力は十分に小さく設定し、絶対にキャッチされないようにする
    D[N + 1] = -INF;

    // 各頂点からの遷移先を決定
    vector<int> nxt(N + 2);
    for (int i = 1; i <= N; ++i) {
        if (L[i] == i && R[i] == i) {
            nxt[i] = N + 1;
        } else if (L[i] < i) {
            nxt[i] = L[i];
        } else {
            nxt[i] = i + 1;
        }
    }
    nxt[N + 1] = N + 1;

    // 逆辺のグラフを構築
    vector<vector<int>> rev(N + 2);
    for (int i = 1; i <= N; ++i) {
        rev[nxt[i]].push_back(i);
    }

    // 各頂点から到達可能な「パス不可の頂点」を BFS で求める
    vector<int> last(N + 2, -1);
    queue<int> q;
    for (int v : rev[N + 1]) {
        if (v <= N) {
            last[v] = v;
            q.push(v);
        }
    }

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int to : rev[u]) {
            if (to <= N && last[to] == -1) {
                last[to] = last[u];
                q.push(to);
            }
        }
    }

    // ダブリングテーブルの構築 (P = 30, 2^30 > 10^9)
    vector<vector<int>> to_dbl(30, vector<int>(N + 2));
    vector<vector<long long>> max_val(30, vector<long long>(N + 2));

    for (int i = 1; i <= N + 1; ++i) {
        to_dbl[0][i] = nxt[i];
        max_val[0][i] = D[i];
    }

    for (int p = 1; p < 30; ++p) {
        for (int i = 1; i <= N + 1; ++i) {
            to_dbl[p][i] = to_dbl[p - 1][to_dbl[p - 1][i]];
            max_val[p][i] = max(max_val[p - 1][i], max_val[p - 1][to_dbl[p - 1][i]] + (1LL << (p - 1)));
        }
    }

    // クエリ処理
    for (int j = 0; j < M; ++j) {
        int T;
        long long W;
        cin >> T >> W;

        int curr = T;
        long long dist = 0;
        for (int p = 29; p >= 0; --p) {
            if (W <= max_val[p][curr] + dist) {
                // この 2^p 歩の間にキャッチされるので、進まない
            } else {
                // 安全に進める
                dist += (1LL << p);
                curr = to_dbl[p][curr];
            }
        }

        // ループ終了時の判定
        if (W <= D[curr] + dist) {
            cout << -1 << "\n";
        } else {
            cout << last[T] << "\n";
        }
    }

    return 0;
}

---

この解説は gemini-3.5-flash-high によって生成されました。