概要

命令列 \(S\) は書き換えられますが、質問 2 ごとにロボットは毎回「部屋 \(1\)・未回収状態・スコア \(0\)」から実行し直します。
制約に \(KQ \leq 2 \times 10^7\) があるため、各質問で命令列全体をそのままシミュレーションしても十分間に合います。

考察

質問 2 のたびに、現在の命令列 \(S\) を先頭から順に実行すれば答えは求められます。

ただし、宝が「すでに回収済みかどうか」を管理する必要があります。

素朴には、質問 2 ごとに

• collected[i] = false として全ての部屋を未回収に戻す
• 命令列 \(S\) をシミュレーションする

という方法が考えられます。

しかし、毎回長さ \(N\) の配列を初期化すると、質問回数を \(K\) として \(O(KN)\) かかります。
\(N\) も \(K\) も最大で \(2 \times 10^5\) 程度になり得るため、これは間に合いません。

そこで、配列を毎回初期化する代わりに「タイムスタンプ」を使います。

collected[i] に「最後に部屋 \(i\) の宝を回収した質問番号」を記録します。
現在処理中の質問番号を stamp とすると、

• collected[pos] == stamp なら、今回のシミュレーションですでに回収済み
• collected[pos] != stamp なら、今回のシミュレーションでは未回収

と判定できます。

これにより、質問ごとに配列全体を初期化する必要がなくなります。

アルゴリズム

現在の命令列 \(S\) を文字列として保持します。

各操作について次のように処理します。

操作 1 p c

命令列の \(p\) 文字目を \(c\) に変更します。

文字列は \(0\) 始まりなので、実装では

S[p - 1] = c;

とします。

操作 2

現在の命令列 \(S\) をシミュレーションします。

1. stamp を \(1\) 増やす
2. ロボットの位置 pos を \(1\) にする
3. 答え ans を \(0\) にする
4. 命令列 \(S\) を先頭から順に見る
5. 各文字に応じて処理する
   • L: pos > 1 なら pos--
   • R: pos < N なら pos++
   • B: pos = 1
   • P:
     • collected[pos] != stamp なら、今回まだ回収していない
     • collected[pos] = stamp として回収済みにする
     • ans += A[pos]
6. ans を出力する

例えば同じ部屋で何度 P を実行しても、collected[pos] == stamp になっているため、加算されるのは最初の \(1\) 回だけです。

計算量

質問 2 の回数を \(K\) とします。

• 時間計算量: \(O(M + KQ)\)
  • 書き換え操作は \(O(1)\)
  • 質問操作では命令列 \(S\) 全体を \(O(Q)\) でシミュレーション
  • 制約より \(KQ \leq 2 \times 10^7\) なので十分高速です
• 空間計算量: \(O(N + Q)\)
  • 宝の価値配列に \(O(N)\)
  • 回収状態管理配列に \(O(N)\)
  • 命令列に \(O(Q)\)

実装のポイント

獲得スコアは最大で宝の価値の総和になり得ます。
\(A_i \leq 10^9\), \(N \leq 2 \times 10^5\) なので、最大値は \(2 \times 10^{14}\) 程度です。

そのため、答えや宝の価値は int ではなく long long で管理します。

また、collected 配列を毎回初期化しないことが重要です。
stamp を使うことで、各質問の開始時に全ての宝が未回収である状態を \(O(1)\) で表現できます。

ソースコード

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

---

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