概要

木構造を成す状態遷移において、各状態での棚から落下した置物の個数を求める問題。累積オフセットの最小値・最大値を管理し、二分探索で生存する置物を数える。

考察

重要な気づき：置物が生き残る条件

置物 \(i\) の初期位置を \(A_i\) とする。状態 \(0\) から状態 \(j\) までのパス上の各状態 \(k\) における累積オフセット（全移動の合計）を \(\text{offset}[k]\) とすると、置物 \(i\) の状態 \(k\) での位置は \(A_i + \text{offset}[k]\) である。

置物が状態 \(j\) で生き残るためには、パス上のすべての状態で位置が \([1, M]\) の範囲内でなければならない。 途中で一度でも落下すれば、コピー時にその置物は含まれないからである。

この条件は次のように書き換えられる：

\[1 \leq A_i + \text{offset}[k] \leq M \quad (\text{パス上のすべての } k)\]

これは以下と同値：

\[A_i + \min_{k} \text{offset}[k] \geq 1 \quad \text{かつ} \quad A_i + \max_{k} \text{offset}[k] \leq M\]

つまり、生存条件は：

\[1 - \text{min\_off}[j] \leq A_i \leq M - \text{max\_off}[j]\]

素朴なアプローチの問題点

各状態ごとに全置物をシミュレーションすると \(O(NQ)\) で TLE になる。しかし上記の観察により、各状態で管理すべきは「累積オフセット」「パス上のオフセット最小値」「パス上のオフセット最大値」の3つだけでよい。

アルゴリズム

1. 初期位置 \(A\) をソートする。
2. 各状態 \(j\) について、親状態 \(P_j\) から以下を \(O(1)\) で計算する：
   • \(\text{offset}[j] = \text{offset}[P_j] \pm D_j\)（方向による）
   • \(\text{min\_off}[j] = \min(\text{min\_off}[P_j],\ \text{offset}[j])\)
   • \(\text{max\_off}[j] = \max(\text{max\_off}[P_j],\ \text{offset}[j])\)
3. 生存する置物は \(A_i \in [\text{lo}, \text{hi}]\)（\(\text{lo} = 1 - \text{min\_off}[j]\), \(\text{hi} = M - \text{max\_off}[j]\)）を満たすもの。ソート済み配列に対して二分探索で個数を求める。
4. 落下数は \(N - \text{(生存数)}\)。

具体例

\(N=3, M=10, A=[2, 5, 9]\) で、状態1が「状態0から右に3移動」、状態2が「状態1から左に6移動」の場合：

• 状態1: offset=3, min_off=0, max_off=3 → 生存範囲 \([1, 7]\) → \(A_i \in \{2,5\}\) が生存、落下1個
• 状態2: offset=-3, min_off=-3, max_off=3 → 生存範囲 \([4, 7]\) → \(A_i \in \{5\}\) が生存、落下2個

計算量

• 時間計算量: \(O(N \log N + Q \log N)\)（ソートに \(O(N \log N)\)、各クエリで二分探索に \(O(\log N)\)）
• 空間計算量: \(O(N + Q)\)

実装のポイント

• オフセットは \(10^9 \times 2 \times 10^5\) 程度まで大きくなりうるので long long を使用する。

• \(\text{lo} > \text{hi}\) のとき（生存可能な範囲が空）は生存数を0とする。

• 状態0の offset, min_off, max_off はすべて0で初期化する。

• 各状態は親からの情報のみで計算できるため、木構造を明示的に構築する必要はなく、入力順に処理すれば十分（\(P_j < j\) が保証されているため）。

  ソースコード

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    long long M;
    int Q;
    cin >> N >> M >> Q;
    
    vector<long long> A(N);
    for(int i = 0; i < N; i++) cin >> A[i];
    
    sort(A.begin(), A.end());
    
    // For each state, store: offset, min_offset along path, max_offset along path
    // State 0: offset=0, min_off=0, max_off=0
    vector<long long> offset(Q+1), min_off(Q+1), max_off(Q+1);
    offset[0] = 0;
    min_off[0] = 0;
    max_off[0] = 0;
    
    for(int j = 1; j <= Q; j++){
        int P;
        char C;
        long long D;
        cin >> P >> C >> D;
        
        if(C == 'R'){
            offset[j] = offset[P] + D;
        } else {
            offset[j] = offset[P] - D;
        }
        min_off[j] = min(min_off[P], offset[j]);
        max_off[j] = max(max_off[P], offset[j]);
        
        // Valid range for A_i: [1 - min_off[j], M - max_off[j]]
        long long lo = 1 - min_off[j];
        long long hi = M - max_off[j];
        
        long long surviving = 0;
        if(lo <= hi){
            // count A_i in [lo, hi]
            auto left = lower_bound(A.begin(), A.end(), lo);
            auto right = upper_bound(A.begin(), A.end(), hi);
            surviving = right - left;
        }
        
        cout << N - surviving << '\n';
    }
    
    return 0;
}

---

この解説は claude4.6opus-thinking によって生成されました。