概要

棚に置かれた \(N\) 個の置物を、コピーと移動（スライド）を繰り返して管理する問題です。移動の結果、棚の範囲 \([1, M]\) からはみ出した置物は取り除かれます。各操作後の状態において、それまでに落下した置物の総数を求めます。

考察

1. 素朴なシミュレーションの限界

各状態ごとにすべての置物の位置を更新し、落下判定を行うと、最悪の場合 \(O(NQ)\) の計算量がかかります。\(N, Q \leq 2 \times 10^5\) であるため、これでは実行時間制限に間に合いません。置物一つひとつを追うのではなく、「どのような初期位置の置物が生き残るか」という条件に注目する必要があります。

2. 生き残るための条件

初期位置を \(A_i\) とします。状態 \(j\) において置物 \(i\) が棚に残っているためには、「状態 0 から状態 \(j\) に至るまでのすべての経路（状態）において、置物の位置が常に \([1, M]\) の範囲内にあること」が条件となります。

状態 \(k\) における初期位置からの累積移動量を \(S_k\) とすると、状態 \(k\) での置物の位置は \(A_i + S_k\) と表せます。このとき、生存条件は以下のようになります。 $\(1 \leq A_i + S_k \leq M\)\( これを \)A_i\( について解くと： \)\(1 - S_k \leq A_i \leq M - S_k\)$

状態 \(j\) において置物が生き残るためには、その祖先となるすべての状態 \(k\) においてこの不等式が満たされる必要があります。つまり、初期位置 \(A_i\) が以下の範囲 \([L_j, R_j]\) に収まっている必要があります。 - \(L_j = \max_{k \in \text{path}(0, j)} (1 - S_k)\) - \(R_j = \min_{k \in \text{path}(0, j)} (M - S_k)\)

3. 状態の遷移と更新

状態 \(j\) は状態 \(P_j\) から作られるため、累積移動量 \(S_j\) や生存範囲 \([L_j, R_j]\) は親の状態の情報を使って効率的に計算できます。 - \(S_j = S_{P_j} + (\text{移動量 } D_j)\) （左移動なら \(-D_j\)、右移動なら \(+D_j\)） - \(L_j = \max(L_{P_j}, 1 - S_j)\) - \(R_j = \min(R_{P_j}, M - S_j)\)

初期状態（状態 0）では \(S_0 = 0, L_0 = 1, R_0 = M\) です。

アルゴリズム

1. 初期位置のソート: 与えられた初期位置 \(A_1, \dots, A_N\) を昇順にソートします。これにより、特定の範囲 \([L, R]\) に含まれる要素の個数を二分探索で高速に数えられるようになります。
2. 各状態の計算: \(j = 1\) から \(Q\) まで順番に以下の処理を行います。
   • 親の状態 \(P_j\) の値を用いて、現在の状態 \(j\) の累積移動量 \(S_j\) と生存範囲 \([L_j, R_j]\) を更新します。
   • ソート済みの \(A\) に対して二分探索（lower_bound, upper_bound 等）を行い、範囲 \([L_j, R_j]\) に含まれる要素数（生き残っている置物の数）を求めます。
   • \(L_j > R_j\) の場合は、生き残っている置物は 0 個です。
3. 出力: 「落下した個数 = \(N - (\text{生き残っている個数})\)」を出力します。

計算量

• 時間計算量: \(O(N \log N + Q \log N)\)
  • 初期位置のソートに \(O(N \log N)\)。
  • 各クエリにつき、二分探索で個数を数えるのに \(O(\log N)\) かかるため、全体で \(O(Q \log N)\)。
• 空間計算量: \(O(N + Q)\)
  • 初期位置の配列 \(A\) と、各状態の \(S, L, R\) を保持する配列が必要です。

実装のポイント

• 累積移動量の型: 移動量 \(D_j\) や棚のサイズ \(M\) が大きいため、累積移動量 \(S_j\) や範囲の境界 \(L_j, R_j\) は 64bit 整数型（C++なら long long）を使用してください。

• 二分探索: C++ の場合、std::lower_bound と std::upper_bound を使うことで、範囲 \([L, R]\) に含まれる要素の個数を upper_bound(R) - lower_bound(L) として簡単に計算できます。

  ソースコード

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

using namespace std;

/**
 * Problem Summary:
 * - We have N ornaments on a shelf of length M (positions 1 to M).
 * - State 0 is the initial configuration.
 * - Each state j (1 to Q) is created from an existing state P_j.
 * - All ornaments in state j are shifted by D_j (left or right).
 * - Ornaments that fall outside [1, M] are removed from that state.
 * - For each state j, we need to find the number of ornaments that fell out.
 *
 * Logic:
 * - An ornament i at initial position A_i survives in state j if and only if
 *   its position at every step along the path from state 0 to state j
 *   remains within the range [1, M].
 * - Let S_k be the cumulative displacement from the initial position in state k.
 *   The position of ornament i in state k is A_i + S_k.
 *   The condition for survival is: 1 <= A_i + S_k <= M for all k in the path.
 *   This is equivalent to: 1 - S_k <= A_i <= M - S_k for all k in the path.
 * - Thus, for state j, there is a valid range [L_j, R_j] for initial positions A_i:
 *   L_j = max(1, max_{k in path} (1 - S_k))
 *   R_j = min(M, min_{k in path} (M - S_k))
 * - Since P_j < j, we can process states in order from 1 to Q and maintain
 *   S_j, L_j, and R_j based on their values at P_j.
 */

int main() {
    // Speed up input and output operations
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    // Read initial positions and sort them for binary search
    vector<int> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }
    sort(A.begin(), A.end());

    // Arrays to store cumulative displacement and the survival range for each state
    // Q can be up to 2*10^5, so we use long long for positions and shifts.
    vector<long long> S(Q + 1);
    vector<long long> L(Q + 1);
    vector<long long> R(Q + 1);

    // Initial values for state 0 (root)
    S[0] = 0;
    L[0] = 1;
    R[0] = M;

    for (int j = 1; j <= Q; ++j) {
        int p;
        char c;
        long long d;
        cin >> p >> c >> d;

        // Calculate shift for the current operation
        long long delta = (c == 'L' ? -d : d);
        
        // Update cumulative shift and survival range based on parent state P_j
        S[j] = S[p] + delta;
        L[j] = max(L[p], 1 - S[j]);
        R[j] = min(R[p], M - S[j]);

        // Count ornaments whose initial position A_i falls within [L_j, R_j]
        int survivors = 0;
        if (L[j] <= R[j]) {
            // Use binary search to find the number of A_i in [L_j, R_j]
            auto it1 = lower_bound(A.begin(), A.end(), L[j]);
            auto it2 = upper_bound(A.begin(), A.end(), R[j]);
            survivors = (int)distance(it1, it2);
        }
        
        // Output the number of fallen ornaments
        cout << N - survivors << "\n";
    }

    return 0;
}

---

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