Overview

The instruction sequence \(S\) is updated over time, and for each query we need to find “the score when the robot executes \(S\) from its initial state.”
Since the constraint \(KQ \leq 2 \times 10^7\) holds, we can simulate the entire instruction sequence for each query.

Analysis

Each time a query operation 2 is issued, the robot starts execution from the following initial state:

• Located in room \(1\)
• Score is \(0\)
• All treasures are uncollected

Therefore, for each query, we can find the answer by simulating the instruction sequence \(S\) from the beginning.

At first glance, you might want to reinitialize the array representing “whether each room’s treasure has been collected” every time a query is issued.
However, since the number of rooms \(N\) can be up to \(2 \times 10^5\), initializing an array of length \(N\) for each query adds an extra \(O(N)\) cost.

For example, if the number of queries is \(K\), naively reinitializing every time results in an overall cost of

\(O(K(N + Q))\)

On the other hand, this problem has the constraint \(KQ \leq 2 \times 10^7\), meaning the simulation part \(O(KQ)\) is designed to fit within the time limit.
Therefore, it is important to perform the initialization of treasure collection states efficiently.

To achieve this, we use a “timestamp” technique.

For each room \(i\), we record in seen[i] which query last collected the treasure from that room.
If the current query number is stamp, then:

• If seen[i] == stamp, the treasure in room \(i\) has already been collected during this query
• If seen[i] != stamp, the treasure in room \(i\) has not yet been collected during this query

This eliminates the need to reinitialize the entire array for each query.

Algorithm

To allow modifications to the instruction sequence \(S\), we manage it as a bytearray instead of a string.

Each operation is processed as follows.

Operation 1 p c

Change the \(p\)-th character of the instruction sequence \(S\) to \(c\).

This simply overwrites one element of the array, so it runs in \(O(1)\).

Operation 2

Simulate the current instruction sequence from start to end.

Prepare the following variables:

• pos: the current room, managed in \(0\)-indexed form
• score: the current score
• stamp: the current query number
• seen[i]: the query number when the treasure in room \(i\) was last collected

During simulation, process each instruction character one by one:

• L:
  • If pos > 0, then pos -= 1
• R:
  • If pos < N - 1, then pos += 1
• P:
  • If seen[pos] != stamp, the treasure has not yet been collected in this query
  • Set seen[pos] = stamp and add score += A[pos]
• B:
  • Set pos = 0

Finally, output score.

For example, even if P is executed multiple times in the same room, since seen[pos] == stamp will hold after the first time, the score is only incremented on the first occurrence.

Complexity

Let \(K\) be the number of operation 2 queries.

• Time complexity: \(O(M + KQ)\)
  • Each update operation takes \(O(1)\)
  • Each query operation takes \(O(Q)\)
  • Since \(KQ \leq 2 \times 10^7\) by the constraint, this is sufficiently fast
• Space complexity: \(O(N + Q)\)
  • \(O(N)\) for managing treasure collection states
  • \(O(Q)\) for storing the instruction sequence

Implementation Notes

• Room numbers are \(1\)-indexed in the input, but using \(0\)-indexed in the implementation makes things easier to handle.

• Initializing with seen = [0] * N for each query may be slow. Instead, manage it by incrementing stamp.

• Since the instruction sequence is updated, using a bytearray instead of a regular Python string allows efficient single-character modifications.

• The score can be as large as \(N \times 10^9\), so 64-bit integers are required. In Python, there is no need to worry about integer overflow.

  Source Code

import sys

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

    N, Q, M = map(int, input().split())
    A = list(map(int, input().split()))
    S = bytearray(input().strip())

    seen = [0] * N
    stamp = 0
    n_last = N - 1

    L = ord('L')
    R = ord('R')
    P = ord('P')
    B = ord('B')

    ans = []

    for _ in range(M):
        line = input().split()
        if line[0] == b'1':
            p = int(line[1]) - 1
            S[p] = line[2][0]
        else:
            stamp += 1
            pos = 0
            score = 0

            for c in S:
                if c == P:
                    if seen[pos] != stamp:
                        seen[pos] = stamp
                        score += A[pos]
                elif c == R:
                    if pos < n_last:
                        pos += 1
                elif c == L:
                    if pos:
                        pos -= 1
                else:
                    pos = 0

            ans.append(str(score))

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

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.