B - Robot's Treasure Collection

Contest Duration: 2026-09-08 20:00:00+0900 - 2026-09-08 21:00:00+0900 (local time) (60 minutes) Back to Home

B - Robot's Treasure Collection Editorial

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 333 点

問題文

高橋君は、1 から N まで番号のついた N 個の部屋が一列に並んだ通路でロボットを操作します。各部屋 i (1 \leq i \leq N) には価値 A_i の宝が 1 つ置かれています。

ロボットには長さ Q の命令列 S が与えられます。ロボットは部屋 1 から出発し、獲得スコア 0 の状態で、命令列を先頭から順に 1 文字ずつ実行します。各文字の意味は次の通りです。

L: 現在の部屋が 1 より大きければ、左（番号が 1 小さい部屋）に移動する。そうでなければ何もしない。
R: 現在の部屋が N より小さければ、右（番号が 1 大きい部屋）に移動する。そうでなければ何もしない。
P: 現在いる部屋の宝がまだ回収されていなければ、その宝を回収し、獲得スコアにその宝の価値を加算する。すでに回収済みであれば何もしない。
B: 部屋 1 に移動する。

青木君は、命令列 S に対して M 回の操作を順に行います。操作は次の 2 種類です。

1 p c: 命令列 S の p 文字目を文字 c に書き換える。
2: 現在の命令列 S をロボットが実行したときの最終的な獲得スコアを求める。

操作 2 のたびに、ロボットは部屋 1 から出発し、すべての宝が未回収かつ獲得スコアが 0 の初期状態から命令列 S を実行します。この実行は質問に答えるためのシミュレーションであり、命令列 S への書き換えを除いて、各操作の結果が他の操作に影響することはありません。

各操作 2 について、答えを出力してください。

制約

1 \leq N \leq 2 \times 10^5
1 \leq Q \leq 10^5
1 \leq M \leq 10^5
1 \leq A_i \leq 10^9
S は L, R, P, B からなる長さ Q の文字列である。
書き換え操作において、1 \leq p \leq Q であり、c は L, R, P, B のいずれかである。
操作 2 は 1 回以上与えられる。
操作 2 の回数を K とすると、KQ \leq 2 \times 10^7 である。
N, Q, M, A_i, p はすべて整数である。

入力

N Q M
A_1 A_2 \dots A_N
S
op_1
op_2
:
op_M

1 行目には、部屋の数 N、命令列の長さ Q、操作の回数 M がスペース区切りで与えられる。
2 行目には、各部屋の宝の価値 A_1, A_2, \dots, A_N がスペース区切りで与えられる。
3 行目には、長さ Q の文字列 S が与えられる。S の各文字は L, R, P, B のいずれかである。
続く M 行のうち j 行目には、j 番目の操作 op_j が与えられる。
書き換え操作の場合、1 p c の形式で与えられる。ここで p は書き換える位置、c は L, R, P, B のいずれかである。
質問操作の場合、2 の形式で与えられる。

出力

各操作 2 について、その時点の命令列 S を実行したときの最終的な獲得スコアを、操作が与えられた順に 1 行ずつ出力してください。

入力例 1

5 8 6
3 10 5 8 2
PRRPLPBR
2
1 2 P
2
1 7 R
1 8 P
2

出力例 1

18
13
13

入力例 2

3 7 7
4 7 9
LLPPRRB
2
1 1 R
2
1 4 B
2
1 7 P
2

出力例 2

入力例 3

10 24 15
6 1 13 8 21 5 34 2 55 3
PRRPRRPLLBPRRPPBLLRPRBRP
2
1 10 R
2
1 1 B
1 18 P
2
1 24 L
2
1 6 B
1 7 R
2
1 15 L
2
1 3 P
2

出力例 3

入力例 4

30 80 25
12 45 7 100 23 56 89 14 67 31 90 4 28 73 11 62 39 85 16 54 200 3 99 41 77 25 68 150 8 33
PRRPLBRRPPBLLRPRBPLRRRPPBPLLRPRRBLPPRRLBPBRRLLPPRBRPLLRRPPBBRPLPBRRPPBLLRPRRLBPP
2
1 6 R
1 20 P
2
1 35 B
1 48 P
2
1 1 L
1 80 B
2
1 12 P
1 13 R
1 14 R
2
1 50 L
1 51 L
2
1 60 P
1 70 B
2
1 25 R
2
1 40 P
1 41 P
2

出力例 4

入力例 5

出力例 5

Score : 333 pts

Problem Statement

Takahashi operates a robot in a corridor consisting of N rooms numbered from 1 to N arranged in a row. Each room i (1 \leq i \leq N) contains one treasure with value A_i.

The robot is given a command sequence S of length Q. The robot starts in room 1 with a score of 0, and executes the command sequence one character at a time from the beginning. The meaning of each character is as follows:

L: If the current room number is greater than 1, move left (to the room with number 1 smaller). Otherwise, do nothing.
R: If the current room number is less than N, move right (to the room with number 1 larger). Otherwise, do nothing.
P: If the treasure in the current room has not yet been collected, collect it and add its value to the score. If it has already been collected, do nothing.
B: Move to room 1.

Aoki performs M operations on the command sequence S in order. There are two types of operations:

1 p c: Replace the p-th character of the command sequence S with character c.
2: Determine the final score when the robot executes the current command sequence S.

For each operation 2, the robot starts from room 1 with all treasures uncollected and a score of 0, and executes the command sequence S from this initial state. This execution is a simulation to answer the query, and apart from the replacements to the command sequence S, the result of each operation does not affect other operations.

For each operation 2, output the answer.

Constraints

1 \leq N \leq 2 \times 10^5
1 \leq Q \leq 10^5
1 \leq M \leq 10^5
1 \leq A_i \leq 10^9
S is a string of length Q consisting of L, R, P, B.
In replacement operations, 1 \leq p \leq Q and c is one of L, R, P, B.
At least one operation 2 is given.
Letting K be the number of operation 2 queries, KQ \leq 2 \times 10^7.
N, Q, M, A_i, p are all integers.

Input

N Q M
A_1 A_2 \dots A_N
S
op_1
op_2
:
op_M

The first line contains the number of rooms N, the length of the command sequence Q, and the number of operations M, separated by spaces.
The second line contains the values of the treasures in each room A_1, A_2, \dots, A_N, separated by spaces.
The third line contains the string S of length Q. Each character of S is one of L, R, P, B.
The following M lines each contain the j-th operation op_j on the j-th line.
For a replacement operation, it is given in the format 1 p c, where p is the position to replace and c is one of L, R, P, B.
For a query operation, it is given in the format 2.

Output

For each operation 2, output the final score when executing the command sequence S at that point, one per line in the order the operations are given.

Sample Input 1

5 8 6
3 10 5 8 2
PRRPLPBR
2
1 2 P
2
1 7 R
1 8 P
2

Sample Output 1

18
13
13

Sample Input 2

3 7 7
4 7 9
LLPPRRB
2
1 1 R
2
1 4 B
2
1 7 P
2

Sample Output 2

Sample Input 3

10 24 15
6 1 13 8 21 5 34 2 55 3
PRRPRRPLLBPRRPPBLLRPRBRP
2
1 10 R
2
1 1 B
1 18 P
2
1 24 L
2
1 6 B
1 7 R
2
1 15 L
2
1 3 P
2

Sample Output 3

Sample Input 4

30 80 25
12 45 7 100 23 56 89 14 67 31 90 4 28 73 11 62 39 85 16 54 200 3 99 41 77 25 68 150 8 33
PRRPLBRRPPBLLRPRBPLRRRPPBPLLRPRRBLPPRRLBPBRRLLPPRBRPLLRRPPBBRPLPBRRPPBLLRPRRLBPP
2
1 6 R
1 20 P
2
1 35 B
1 48 P
2
1 1 L
1 80 B
2
1 12 P
1 13 R
1 14 R
2
1 50 L
1 51 L
2
1 60 P
1 70 B
2
1 25 R
2
1 40 P
1 41 P
2

Sample Output 4

Sample Input 5

Sample Output 5