Overview

The instruction sequence \(S\) can be rewritten, but for each query 2, the robot always restarts execution from “room \(1\), nothing collected, score \(0\).”
Since the constraint \(KQ \leq 2 \times 10^7\) is given, directly simulating the entire instruction sequence for each query is fast enough.

Analysis

For each query 2, we can obtain the answer by executing the current instruction sequence \(S\) from the beginning in order.

However, we need to keep track of whether each treasure has “already been collected or not.”

A naive approach for each query 2 would be:

• Reset all rooms to uncollected by setting collected[i] = false
• Simulate the instruction sequence \(S\)

However, reinitializing an array of length \(N\) every time costs \(O(KN)\), where \(K\) is the number of queries.
Since both \(N\) and \(K\) can be up to about \(2 \times 10^5\), this is too slow.

Instead of reinitializing the array every time, we use a “timestamp” technique.

We record in collected[i] the “query number when the treasure in room \(i\) was last collected.”
If stamp is the query number currently being processed, then:

• If collected[pos] == stamp, the treasure has already been collected in the current simulation
• If collected[pos] != stamp, the treasure has not yet been collected in the current simulation

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

Algorithm

We maintain the current instruction sequence \(S\) as a string.

Each operation is processed as follows.

Operation 1 p c

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

Since the string is \(0\)-indexed in the implementation, we write:

S[p - 1] = c;

Operation 2

Simulate the current instruction sequence \(S\).

1. Increment stamp by \(1\)
2. Set the robot’s position pos to \(1\)
3. Set the answer ans to \(0\)
4. Iterate through the instruction sequence \(S\) from the beginning
5. Process each character accordingly:
   • L: If pos > 1, then pos--
   • R: If pos < N, then pos++
   • B: pos = 1
   • P:
     • If collected[pos] != stamp, the treasure has not been collected yet in this simulation
     • Set collected[pos] = stamp to mark it as collected
     • ans += A[pos]
6. Output ans

For example, even if P is executed multiple times in the same room, since collected[pos] == stamp after the first time, the score is only added once.

Complexity

Let \(K\) be the number of query 2 operations.

• Time complexity: \(O(M + KQ)\)
  • Each rewrite operation is \(O(1)\)
  • Each query operation simulates the entire instruction sequence \(S\) in \(O(Q)\)
  • Since the constraint guarantees \(KQ \leq 2 \times 10^7\), this is fast enough
• Space complexity: \(O(N + Q)\)
  • \(O(N)\) for the treasure value array
  • \(O(N)\) for the collection status management array
  • \(O(Q)\) for the instruction sequence

Implementation Notes

The maximum possible score is the total sum of all treasure values.
Since \(A_i \leq 10^9\) and \(N \leq 2 \times 10^5\), the maximum value can be around \(2 \times 10^{14}\).

Therefore, the answer and treasure values should be stored using long long instead of int.

Also, it is crucial not to reinitialize the collected array every time.
By using stamp, we can represent the state where all treasures are uncollected at the start of each query in \(O(1)\).

Source Code

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

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

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

    vector<long long> A(N + 1);
    for (int i = 1; i <= N; i++) cin >> A[i];

    string S;
    cin >> S;

    vector<int> collected(N + 1, 0);
    int stamp = 0;

    for (int i = 0; i < M; i++) {
        int type;
        cin >> type;

        if (type == 1) {
            int p;
            char c;
            cin >> p >> c;
            S[p - 1] = c;
        } else {
            stamp++;
            int pos = 1;
            long long ans = 0;

            for (char c : S) {
                if (c == 'L') {
                    if (pos > 1) pos--;
                } else if (c == 'R') {
                    if (pos < N) pos++;
                } else if (c == 'B') {
                    pos = 1;
                } else if (c == 'P') {
                    if (collected[pos] != stamp) {
                        collected[pos] = stamp;
                        ans += A[pos];
                    }
                }
            }

            cout << ans << '\n';
        }
    }

    return 0;
}

---

This editorial was generated by gpt-5.5-xhigh.