Overview

Each state is determined by the sequence of operations from state \(0\) to that state.
We derive the condition for each figurine to remain until the end from the “minimum and maximum of cumulative displacement,” and use binary search to count the number of initial positions \(A_i\) satisfying the condition.

Analysis

States branch through copying, but since state \(j\) is always created from state \(P_j\), the structure forms a tree rooted at state \(0\).

When considering a particular state \(j\), only the operations performed along the path from state \(0\) to state \(j\) matter.

For example, consider the cumulative displacement due to operations.

• A move right by \(D\) contributes \(+D\)
• A move left by \(D\) contributes \(-D\)

Let \(S_j\) be the cumulative displacement at state \(j\). Then, the current position of a figurine with initial position \(A_i\) is

\(A_i + S_j\)

However, if a figurine ever goes outside the shelf at any point, it falls and disappears.
In other words, for all intermediate states up to state \(j\), the position must be between \(1\) and \(M\) inclusive.

Let \(\mathrm{mn}_j\) be the minimum and \(\mathrm{mx}_j\) be the maximum of the cumulative displacement from state \(0\) to state \(j\).

Then, the condition for a figurine with initial position \(A_i\) to survive until the end is that

\(1 \leq A_i + x \leq M\)

holds for all cumulative displacements \(x\) along the path.

The leftmost position occurs when the cumulative displacement is \(\mathrm{mn}_j\), so from

\(1 \leq A_i + \mathrm{mn}_j\)

we need

\(A_i \geq 1 - \mathrm{mn}_j\)

Also, the rightmost position occurs when the cumulative displacement is \(\mathrm{mx}_j\), so from

\(A_i + \mathrm{mx}_j \leq M\)

we need

\(A_i \leq M - \mathrm{mx}_j\)

Therefore, the figurines remaining in state \(j\) are those whose initial position \(A_i\) falls within the interval

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

Naively checking all figurines for each state would be \(O(NQ)\), which can be up to about \(4 \times 10^{10}\) and is too slow.

Instead, we sort the initial positions \(A_i\) in advance and use binary search to find the count of positions within the interval for each state.

Algorithm

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

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

• \(\mathrm{sum}_j\): the cumulative displacement from state \(0\) to state \(j\)
• \(\mathrm{mn}_j\): the minimum cumulative displacement along the path
• \(\mathrm{mx}_j\): the maximum cumulative displacement along the path

Since state \(j\) is created from state \(P_j\), if we let \(\delta\) be the displacement due to the operation:

• R D gives \(\delta = D\)
• L D gives \(\delta = -D\)

Thus,

\(\mathrm{sum}_j = \mathrm{sum}_{P_j} + \delta\)

The minimum and maximum can be updated from the parent state’s information and the current cumulative displacement:

\(\mathrm{mn}_j = \min(\mathrm{mn}_{P_j}, \mathrm{sum}_j)\)

\(\mathrm{mx}_j = \max(\mathrm{mx}_{P_j}, \mathrm{sum}_j)\)

With this, the range of initial positions for figurines remaining in state \(j\) is

\(L = 1 - \mathrm{mn}_j\)

\(R = M - \mathrm{mx}_j\)

If \(L > R\), no figurines remain.

Otherwise, using the sorted array \(A\):

• lower_bound(A, L): the first position that is \(\geq L\)
• upper_bound(A, R): the first position that exceeds \(R\)

we can find the count of elements within the interval \([L, R]\).

This count is the number of remaining figurines, so the answer is

\(N - \text{remain}\)

Complexity

• Time complexity: \(O(N \log N + Q \log N)\)
• Space complexity: \(O(N + Q)\)

Implementation Notes

The cumulative displacement can be as large as \(2 \times 10^5 \times 10^9 = 2 \times 10^{14}\).
Therefore, long long must be used instead of int.

Also, since \(P_j\) is always less than \(j\), processing in input order guarantees that the parent state’s information has already been computed.

Source Code

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    long long M;
    cin >> N >> M >> Q;

    vector<long long> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    sort(A.begin(), A.end());

    vector<long long> sum(Q + 1, 0), mn(Q + 1, 0), mx(Q + 1, 0);

    for (int j = 1; j <= Q; j++) {
        int P;
        char C;
        long long D;
        cin >> P >> C >> D;

        long long delta = (C == 'R' ? D : -D);

        sum[j] = sum[P] + delta;
        mn[j] = min(mn[P], sum[j]);
        mx[j] = max(mx[P], sum[j]);

        long long L = 1 - mn[j];
        long long R = M - mx[j];

        long long remain = 0;
        if (L <= R) {
            remain = upper_bound(A.begin(), A.end(), R) - lower_bound(A.begin(), A.end(), L);
        }

        cout << N - remain << '\n';
    }

    return 0;
}

---

This editorial was generated by gpt-5.5-xhigh.