まず、\(A\) をソートすると、各操作により残る \(A\) の集合は区間となります。さらに、この区間は「左に最大どれだけ減ったか」「右に最大どれだけ増えたか」の \(2\) つの情報から復元できます。これらの情報は現在どれだけ状態 \(0\) からずれているか・それらの累積 min / max を保持することで計算できます。

これらの情報から二分探索を用いることで棚から落下した置物の個数を求めることができます。

実装例(Python3)

input = __import__("sys").stdin.readline
import bisect

n, m, q = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
sum_d = [0]
sum_d_min = [0]
sum_d_max = [0]
for _ in range(q):
    pp, c, dd = map(str, input().split())
    p = int(pp)
    d = int(dd)
    sum_d.append(sum_d[p] + (d if c == "R" else -d))
    sum_d_min.append(min(sum_d_min[p], sum_d[-1]))
    sum_d_max.append(max(sum_d_max[p], sum_d[-1]))
    l, r = -sum_d_min[-1], sum_d_max[-1]
    if l + r >= m:
        print(n)
        continue
    remain = bisect.bisect_right(a, m - r) - bisect.bisect_left(a, l + 1)
    print(n - remain)