概要

命令列 S への1文字更新を受けながら、問い合わせごとに「最初からロボットを実行したときの得点」を求める問題です。
制約のポイントは \(KQ \le 2\times 10^7\)（2 の回数を \(K\)）なので、各問い合わせを \(O(Q)\) で素直にシミュレーションすれば間に合います。

考察

重要な観察は次の2つです。

1. 各 2 クエリは独立
   問題文にある通り、2 のたびに

   • 位置は部屋1
   • 宝は全て未回収
   • スコア0
     に戻ります。
     つまり前回の問い合わせ結果を引き継ぐ必要がありません。

2. 制約が「全問い合わせでの総シミュレーション量」を保証している
   1回の 2 で命令列を先頭から読むと \(O(Q)\)。
   これを \(K\) 回行うと \(O(KQ)\) ですが、問題が \(KQ \le 2\times10^7\) を保証しているため十分実行可能です。

---

素朴に見える実装でも、1点だけ注意が必要です。
各問い合わせで「どの部屋の宝を回収済みか」を毎回 vector<bool>(N) などで初期化すると、初期化コストが毎回 \(O(N)\) かかります。
すると全体で \(O(K(N+Q))\) になり、場合によって重くなります。

そこでコードでは タイムスタンプ法 を使っています。

• seen[i] に「最後に部屋 \(i\) を回収した問い合わせ番号」を記録
• 今回の問い合わせ番号を mark とする
• seen[pos] != mark なら未回収、回収して seen[pos] = mark

これで、問い合わせごとに seen 全体を初期化せずに済みます。

アルゴリズム

更新操作 1 p c

• S[p-1] = c と1文字書き換えるだけ（\(O(1)\)）。

問い合わせ操作 2

以下をシミュレーションする（\(O(Q)\)）。

1. pos = 1, score = 0 で開始
2. 命令列 S を先頭から順に見る
   • L: pos > 1 なら pos--
   • R: pos < N なら pos++
   • B: pos = 1
   • P: その問い合わせでまだ pos の宝を取っていなければ加点
3. 最終 score を出力

回収判定（タイムスタンプ法）

• cur_mark を問い合わせごとに増やす
• 今回の値を mark = cur_mark とする
• P のとき：
  • seen[pos] != mark なら未回収 → seen[pos] = mark, score += A[pos]
  • それ以外は何もしない

（コードでは cur_mark == INT_MAX のときだけ seen を全0に戻して安全にしています。）

計算量

• 時間計算量:
  
  • 更新1回あたり \(O(1)\)
    
  • 問い合わせ1回あたり \(O(Q)\)
    
  • 全体で \(O(M + KQ)\)（実質 \(O(KQ)\) が支配的）
• 空間計算量: \(O(N + Q)\)（A, S, seen）

実装のポイント

• S は C++ の string で持ち、更新は S[p-1] に直接代入。

• 得点は最大で \(N \times 10^9\) になりうるため long long を使う。

• seen の毎回初期化を避けるため、タイムスタンプ法を使う。これが高速化の肝です。

  ソースコード

#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;
}

---

この解説は gpt-5.3-codex によって生成されました。