概要

各状態は、状態 \(0\) からその状態までの操作列によって決まります。
各置物が最後まで残る条件を「累積移動量の最小値・最大値」から求め、初期位置 \(A_i\) が条件を満たす個数を二分探索で数えます。

考察

状態はコピーによって分岐しますが、状態 \(j\) は必ず状態 \(P_j\) から作られるので、状態 \(0\) を根とする木のような構造になります。

ある状態 \(j\) について考えると、状態 \(0\) から状態 \(j\) までのパス上で行われた操作だけが重要です。

例えば、操作による累積移動量を考えます。

• 右に \(D\) 移動する操作は \(+D\)
• 左に \(D\) 移動する操作は \(-D\)

とします。

状態 \(j\) における累積移動量を \(S_j\) とすると、初期位置が \(A_i\) の置物の現在位置は

\(A_i + S_j\)

です。

ただし、置物は途中で一度でも棚の外に出ると落下して消えます。
つまり、状態 \(j\) までのすべての途中状態について、位置が \(1\) 以上 \(M\) 以下である必要があります。

状態 \(0\) から状態 \(j\) までの累積移動量の最小値を \(\mathrm{mn}_j\)、最大値を \(\mathrm{mx}_j\) とします。

すると、初期位置 \(A_i\) の置物が最後まで残る条件は、

\(1 \leq A_i + x \leq M\)

が、すべての累積移動量 \(x\) に対して成り立つことです。

最も左に行くのは累積移動量が \(\mathrm{mn}_j\) のときなので、

\(1 \leq A_i + \mathrm{mn}_j\)

より、

\(A_i \geq 1 - \mathrm{mn}_j\)

が必要です。

また、最も右に行くのは累積移動量が \(\mathrm{mx}_j\) のときなので、

\(A_i + \mathrm{mx}_j \leq M\)

より、

\(A_i \leq M - \mathrm{mx}_j\)

が必要です。

したがって、状態 \(j\) で残っている置物は、初期位置 \(A_i\) が区間

\([1 - \mathrm{mn}_j,\ M - \mathrm{mx}_j]\)

に含まれるものです。

素朴に各状態ごとにすべての置物を確認すると \(O(NQ)\) となり、最大で \(4 \times 10^{10}\) 程度になってしまうため間に合いません。

そこで、初期位置 \(A_i\) をあらかじめソートしておき、各状態ごとに区間内に含まれる個数を二分探索で求めます。

アルゴリズム

まず、初期位置列 \(A\) を昇順にソートします。

各状態 \(j\) について、以下を管理します。

• \(\mathrm{sum}_j\)：状態 \(0\) から状態 \(j\) までの累積移動量
• \(\mathrm{mn}_j\)：そのパス上での累積移動量の最小値
• \(\mathrm{mx}_j\)：そのパス上での累積移動量の最大値

状態 \(j\) は状態 \(P_j\) から作られるので、操作による移動量を \(\delta\) とすると、

• R D なら \(\delta = D\)
• L D なら \(\delta = -D\)

です。

よって、

\(\mathrm{sum}_j = \mathrm{sum}_{P_j} + \delta\)

となります。

また、最小値・最大値は親状態までの情報と現在の累積移動量から更新できます。

\(\mathrm{mn}_j = \min(\mathrm{mn}_{P_j}, \mathrm{sum}_j)\)

\(\mathrm{mx}_j = \max(\mathrm{mx}_{P_j}, \mathrm{sum}_j)\)

これにより、状態 \(j\) で残る置物の初期位置の範囲は

\(L = 1 - \mathrm{mn}_j\)

\(R = M - \mathrm{mx}_j\)

です。

もし \(L > R\) なら、残る置物は存在しません。

そうでなければ、ソート済みの \(A\) に対して

• lower_bound(A, L)：\(L\) 以上となる最初の位置
• upper_bound(A, R)：\(R\) 以下を超えた最初の位置

を使うことで、区間 \([L, R]\) に含まれる個数を求められます。

これが残っている置物の数なので、答えは

\(N - \text{remain}\)

です。

計算量

• 時間計算量: \(O(N \log N + Q \log N)\)
• 空間計算量: \(O(N + Q)\)

実装のポイント

累積移動量は、最大で \(2 \times 10^5 \times 10^9 = 2 \times 10^{14}\) 程度になる可能性があります。
そのため、int ではなく long long を使う必要があります。

また、状態 \(P_j\) は必ず \(j\) より小さいため、入力順に処理すれば親状態の情報はすでに計算済みです。

ソースコード

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

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

    int N, Q;
    long long M;
    cin >> N >> M >> Q;

    vector<long long> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    sort(A.begin(), A.end());

    vector<long long> sum(Q + 1, 0), mn(Q + 1, 0), mx(Q + 1, 0);

    for (int j = 1; j <= Q; j++) {
        int P;
        char C;
        long long D;
        cin >> P >> C >> D;

        long long delta = (C == 'R' ? D : -D);

        sum[j] = sum[P] + delta;
        mn[j] = min(mn[P], sum[j]);
        mx[j] = max(mx[P], sum[j]);

        long long L = 1 - mn[j];
        long long R = M - mx[j];

        long long remain = 0;
        if (L <= R) {
            remain = upper_bound(A.begin(), A.end(), R) - lower_bound(A.begin(), A.end(), L);
        }

        cout << N - remain << '\n';
    }

    return 0;
}

---

この解説は gpt-5.5-xhigh によって生成されました。