Overview

Each state is created by “copying the parent state and shifting everything left or right.”
We determine whether each figurine remains without falling by using only the minimum and maximum cumulative displacement from the root state.

Analysis

State \(j\) is created by performing one operation from state \(P_j\).
Viewing this as a tree rooted at state \(0\), state \(j\) is the result of sequentially performing the operations along the path from the root to \(j\).

Let the initial position of a figurine be \(a\).
Consider the cumulative displacement along the path from the root to state \(j\).

For example, if we move right by \(3\), left by \(5\), then right by \(2\), the cumulative displacements are

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

The position of the figurine at each point in time is

\[ a + \text{cumulative displacement} \]

For the figurine to remain in state \(j\), it must stay within the shelf range \([1, M]\) at all intermediate points.
In other words, if we denote all cumulative displacements from the root to state \(j\) as \(x\), then

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

must hold for all \(x\).

The key insight here is that we don’t need to remember all cumulative displacements — we only need the minimum and maximum values.

Let the minimum cumulative displacement be \(\mathrm{mn}\) and the maximum be \(\mathrm{mx}\). Then:

• Condition for not falling off the left:

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

i.e.,

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

• Condition for not falling off the right:

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

i.e.,

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

Therefore, the initial positions \(a\) of figurines remaining in state \(j\) are exactly those satisfying

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

---

Naively managing the positions of all figurines for each state would cost \(O(NQ)\) for \(Q\) states and \(N\) figurines.
Since the constraints give \(N,Q \leq 2 \times 10^5\), this is too slow.

Instead, for each state we only maintain:

• The current cumulative displacement
• The minimum cumulative displacement from the root to that state
• The maximum cumulative displacement from the root to that state

Then, by sorting the initial positions \(A_i\) in advance, we can use binary search to count the number of figurines within the interval

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

Algorithm

First, sort the initial position array \(A\).

For each state \(j\), maintain the following values:

• \(\mathrm{offset}[j]\): the cumulative displacement at state \(j\)
• \(\mathrm{min\_offset}[j]\): the minimum cumulative displacement from state \(0\) to state \(j\)
• \(\mathrm{max\_offset}[j]\): the maximum cumulative displacement from state \(0\) to state \(j\)

At state \(0\), nothing has been moved yet, so all values are \(0\).

Let the parent of state \(j\) be \(p = P_j\).

If the operation moves left by \(D_j\):

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

If the operation moves right by \(D_j\):

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

Then, update the minimum and maximum:

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

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

The initial positions of figurines remaining in this state are those satisfying

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

Therefore,

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

and we use binary search on the sorted array \(A\) to count the number of elements within \([left, right]\).

In Python:

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

The number of fallen figurines is

\[ N - \mathrm{remain} \]

Complexity

• Time complexity: \(O((N + Q) \log N)\)
  • Sorting initial positions: \(O(N \log N)\)
  • Binary search for each query: \(O(Q \log N)\)
• Space complexity: \(O(N + Q)\)
  • Sorted initial position array: \(O(N)\)
  • Cumulative displacement, minimum, and maximum for each state: \(O(Q)\)

Implementation Notes

The cumulative displacement can become large in absolute value because there may be many operations and each \(D_j\) can be large.
In Python, integers have arbitrary precision so this is not an issue, but in C++ etc., you need to use long long.

If the interval \([left, right]\) is empty, i.e.,

\[ left > right \]

then the number of remaining figurines is \(0\).

Also, since the interval includes both endpoints, in binary search we use:

• The first position greater than or equal to the left endpoint: bisect_left(A, left)

• The position just after the last position less than or equal to the right endpoint: bisect_right(A, right)

  Source Code

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()

---

This editorial was generated by gpt-5.5-high.