Overview

This problem requires answering queries about “the score when running the robot from the beginning” while processing single-character updates to the instruction sequence S.
The key constraint is \(KQ \le 2\times 10^7\) (where \(K\) is the number of 2 queries), so straightforwardly simulating each query in \(O(Q)\) is fast enough.

Observations

The two important observations are:

1. Each 2 query is independent
   As stated in the problem, for each 2 query:

   • Position resets to room 1
   • All treasures are uncollected
   • Score is 0
     In other words, there is no need to carry over results from previous queries.

2. The constraint guarantees the “total simulation cost across all queries”
   A single 2 query reads the instruction sequence from the beginning in \(O(Q)\).
   Doing this \(K\) times gives \(O(KQ)\), but since the problem guarantees \(KQ \le 2\times10^7\), this is sufficiently feasible.

---

Even with a seemingly naive implementation, there is one point that requires attention.
If you initialize vector<bool>(N) or similar for “which rooms’ treasures have been collected” at each query, the initialization cost is \(O(N)\) each time.
This results in \(O(K(N+Q))\) overall, which can be too slow in some cases.

Therefore, the code uses the timestamp method.

• seen[i] records “the query number when room \(i\)’s treasure was last collected”
• Let mark be the current query number
• If seen[pos] != mark, the treasure is uncollected; collect it and set seen[pos] = mark

This eliminates the need to initialize the entire seen array for each query.

Algorithm

Update operation 1 p c

• Simply replace one character with S[p-1] = c (\(O(1)\)).

Query operation 2

Simulate the following (\(O(Q)\)):

1. Start with pos = 1, score = 0
2. Read the instruction sequence S from the beginning in order
   • L: if pos > 1, then pos--
   • R: if pos < N, then pos++
   • B: pos = 1
   • P: if the treasure at pos hasn’t been collected in this query yet, add points
3. Output the final score

Collection check (timestamp method)

• Increment cur_mark for each query
• Let mark = cur_mark for the current query
• When encountering P:
  • If seen[pos] != mark, it’s uncollected → set seen[pos] = mark, score += A[pos]
  • Otherwise, do nothing

(In the code, when cur_mark == INT_MAX, seen is reset entirely to 0 for safety.)

Complexity

• Time complexity:
  
  • \(O(1)\) per update
    
  • \(O(Q)\) per query
    
  • \(O(M + KQ)\) overall (effectively dominated by \(O(KQ)\))
• Space complexity: \(O(N + Q)\) (A, S, seen)

Implementation Notes

• S is stored as a C++ string, and updates are done by directly assigning to S[p-1].

• The score can be as large as \(N \times 10^9\), so use long long.

• Use the timestamp method to avoid reinitializing seen every time. This is the key to optimization.

  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; // 0-indexed

    vector<int> seen(N + 1, 0);
    int cur_mark = 1;

    auto query = [&]() -> long long {
        if (cur_mark == INT_MAX) {
            fill(seen.begin(), seen.end(), 0);
            cur_mark = 1;
        }
        int mark = cur_mark++;
        int pos = 1;
        long long score = 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 { // 'P'
                if (seen[pos] != mark) {
                    seen[pos] = mark;
                    score += A[pos];
                }
            }
        }
        return score;
    };

    for (int i = 0; i < M; i++) {
        int t;
        cin >> t;
        if (t == 1) {
            int p;
            char c;
            cin >> p >> c;
            S[p - 1] = c;
        } else {
            cout << query() << '\n';
        }
    }

    return 0;
}

---

This editorial was generated by gpt-5.3-codex.