概要

各状態は「親状態をコピーして全体を左右に動かす」ことで作られます。
各置物が落ちずに残る条件を、状態の根からの累積移動量の最小値・最大値だけで判定します。

考察

状態 \(j\) は、状態 \(P_j\) から 1 回操作して作られます。
これを状態 \(0\) を根とする木と見ると、状態 \(j\) は根から \(j\) までのパス上の操作を順に行った結果です。

ある置物の初期位置を \(a\) とします。
根から状態 \(j\) までの途中での累積移動量を考えます。

例えば、右に \(3\)、左に \(5\)、右に \(2\) 動かしたなら、累積移動量は

\[ 0,\ 3,\ -2,\ 0 \]

のようになります。

置物のその時点での位置は

\[ a + \text{累積移動量} \]

です。

置物が状態 \(j\) で残っているためには、途中のすべての時点で棚の範囲 \([1, M]\) に入っている必要があります。
つまり、根から状態 \(j\) までの累積移動量をすべて \(x\) とすると、

\[ 1 \leq a + x \leq M \]

がすべての \(x\) について成り立つ必要があります。

ここで重要なのは、すべての累積移動量を覚える必要はなく、最小値と最大値だけ分かればよいことです。

累積移動量の最小値を \(\mathrm{mn}\)、最大値を \(\mathrm{mx}\) とすると、

• 左にはみ出さない条件：

\[ a + \mathrm{mn} \geq 1 \]

つまり

\[ a \geq 1 - \mathrm{mn} \]

• 右にはみ出さない条件：

\[ a + \mathrm{mx} \leq M \]

つまり

\[ a \leq M - \mathrm{mx} \]

です。

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

\[ 1 - \mathrm{mn} \leq a \leq M - \mathrm{mx} \]

を満たすものだけです。

---

素朴に各状態ごとにすべての置物の位置を管理すると、状態数 \(Q\)、置物数 \(N\) に対して \(O(NQ)\) かかってしまいます。
制約では \(N,Q \leq 2 \times 10^5\) なので間に合いません。

そこで、各状態について

• 現在の累積移動量
• 根からその状態までの累積移動量の最小値
• 根からその状態までの累積移動量の最大値

だけを管理します。

そして、初期位置 \(A_i\) をソートしておけば、区間

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

に含まれる置物の個数を二分探索で求められます。

アルゴリズム

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

各状態 \(j\) について、以下の値を持ちます。

• \(\mathrm{offset}[j]\)：状態 \(j\) における累積移動量
• \(\mathrm{min\_offset}[j]\)：状態 \(0\) から状態 \(j\) までの累積移動量の最小値
• \(\mathrm{max\_offset}[j]\)：状態 \(0\) から状態 \(j\) までの累積移動量の最大値

状態 \(0\) ではまだ何も動かしていないので、すべて \(0\) です。

状態 \(j\) の親を \(p = P_j\) とします。

操作が左に \(D_j\) なら、

\[ \mathrm{offset}[j] = \mathrm{offset}[p] - D_j \]

操作が右に \(D_j\) なら、

\[ \mathrm{offset}[j] = \mathrm{offset}[p] + D_j \]

です。

そして、最小値・最大値を更新します。

\[ \mathrm{min\_offset}[j] = \min(\mathrm{min\_offset}[p], \mathrm{offset}[j]) \]

\[ \mathrm{max\_offset}[j] = \max(\mathrm{max\_offset}[p], \mathrm{offset}[j]) \]

この状態で残っている置物の初期位置は

\[ 1 - \mathrm{min\_offset}[j] \leq A_i \leq M - \mathrm{max\_offset}[j] \]

を満たすものです。

よって、

left = 1 - min_offset[j]
right = M - max_offset[j]

として、ソート済み配列 \(A\) から \([left, right]\) に含まれる要素数を二分探索で求めます。

Python では、

remain = bisect_right(A, right) - bisect_left(A, left)

で求められます。

落下した置物の個数は

\[ N - \mathrm{remain} \]

です。

計算量

• 時間計算量: \(O((N + Q) \log N)\)
  • 初期位置のソートに \(O(N \log N)\)
  • 各クエリで二分探索を行うので \(O(Q \log N)\)
• 空間計算量: \(O(N + Q)\)
  • ソート済みの初期位置列に \(O(N)\)
  • 各状態の累積移動量・最小値・最大値に \(O(Q)\)

実装のポイント

累積移動量は、操作回数が多く、各 \(D_j\) も大きいため、絶対値が大きくなる可能性があります。
Python では整数が任意精度なので問題ありませんが、C++ などでは long long を使う必要があります。

区間 \([left, right]\) が空、つまり

\[ left > right \]

の場合、残っている置物は \(0\) 個です。

また、区間は両端を含むので、二分探索では

• 左端以上の最初の位置：bisect_left(A, left)
• 右端以下の最後の次の位置：bisect_right(A, right)

を使います。

ソースコード

import sys
from bisect import bisect_left, bisect_right

def main():
    input = sys.stdin.buffer.readline

    N, M, Q = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()

    offset = [0] * (Q + 1)
    min_offset = [0] * (Q + 1)
    max_offset = [0] * (Q + 1)

    ans = []
    bl = bisect_left
    br = bisect_right

    for j in range(1, Q + 1):
        p, c, d = input().split()
        p = int(p)
        d = int(d)

        if c == b'L':
            cur = offset[p] - d
        else:
            cur = offset[p] + d

        offset[j] = cur

        mn = min_offset[p]
        mx = max_offset[p]
        if cur < mn:
            mn = cur
        if cur > mx:
            mx = cur

        min_offset[j] = mn
        max_offset[j] = mx

        left = 1 - mn
        right = M - mx

        if left <= right:
            remain = br(A, right) - bl(A, left)
        else:
            remain = 0

        ans.append(str(N - remain))

    sys.stdout.write("\n".join(ans))

if __name__ == "__main__":
    main()

---

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