実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 500 点
問題文
左から右に向かって 1 から N の番号がついた N 個のマスがあります。 各マスには文字が書かれており、マス i には文字 s_i が書かれています。また、各マスにははじめ 1 体のゴーレムがいます。
すぬけ君は Q 回呪文を唱え、ゴーレムたちを移動させました。
i 番目の呪文は文字 t_i と d_i からなり、d_i は L
か R
のいずれかです。
すぬけ君がこの呪文を唱えると、t_i が書かれた全てのマスについて、そのマスにいる全てのゴーレムが隣接するマスに移動します。移動する方向は d_i が L
ならば左、R
ならば右です。
ただし、マス 1 から左に移動しようとしたゴーレムと、マス N から右に移動しようとしたゴーレムは消滅します。
Q 回の呪文詠唱後に消滅していないゴーレムの総数を求めてください。
制約
- 1 \leq N,Q \leq 2 \times 10^{5}
- |s| = N
- s_i,t_i は英大文字
- d_i は
L
またはR
入力
入力は以下の形式で標準入力から与えられる。
N Q s t_1 d_1 \vdots t_{Q} d_Q
出力
答えを出力せよ。
入力例 1
3 4 ABC A L B L B R A R
出力例 1
2
- はじめ、各マスに 1 体のゴーレムがいます。
- 1 番目の呪文では、マス 1 にいるゴーレムが左に移動しようとし、消滅します。
- 2 番目の呪文では、マス 2 にいるゴーレムが左に移動します。
- 3 番目の呪文では、移動するゴーレムはいません。
- 4 番目の呪文では、マス 1 にいるゴーレムが右に移動します。
- 4 回の呪文詠唱後、マス 2 に 1 体、マス 3 に 1 体のゴーレムがいるため、消滅していないゴーレムは 2 体です。
入力例 2
8 3 AABCBDBA A L B R A R
出力例 2
5
- 3 回の呪文詠唱後、マス 2 に 1 体、マス 4 に 2 体、マス 6 に 2 体のゴーレムがいるため、消滅していないゴーレムは 5 体です。
- 1 つの呪文で複数のゴーレムが移動しうることに注意してください。
入力例 3
10 15 SNCZWRCEWB B R R R E R W R Z L S R Q L W L B R C L A L N L E R Z L S L
出力例 3
3
Score : 500 points
Problem Statement
There are N squares numbered 1 to N from left to right. Each square has a character written on it, and Square i has a letter s_i. Besides, there is initially one golem on each square.
Snuke cast Q spells to move the golems.
The i-th spell consisted of two characters t_i and d_i, where d_i is L
or R
.
When Snuke cast this spell, for each square with the character t_i, all golems on that square moved to the square adjacent to the left if d_i is L
, and moved to the square adjacent to the right if d_i is R
.
However, when a golem tried to move left from Square 1 or move right from Square N, it disappeared.
Find the number of golems remaining after Snuke cast the Q spells.
Constraints
- 1 \leq N,Q \leq 2 \times 10^{5}
- |s| = N
- s_i and t_i are uppercase English letters.
- d_i is
L
orR
.
Input
Input is given from Standard Input in the following format:
N Q s t_1 d_1 \vdots t_{Q} d_Q
Output
Print the answer.
Sample Input 1
3 4 ABC A L B L B R A R
Sample Output 1
2
- Initially, there is one golem on each square.
- In the first spell, the golem on Square 1 tries to move left and disappears.
- In the second spell, the golem on Square 2 moves left.
- In the third spell, no golem moves.
- In the fourth spell, the golem on Square 1 moves right.
- After the four spells are cast, there is one golem on Square 2 and one golem on Square 3, for a total of two golems remaining.
Sample Input 2
8 3 AABCBDBA A L B R A R
Sample Output 2
5
- After the three spells are cast, there is one golem on Square 2, two golems on Square 4 and two golems on Square 6, for a total of five golems remaining.
- Note that a single spell may move multiple golems.
Sample Input 3
10 15 SNCZWRCEWB B R R R E R W R Z L S R Q L W L B R C L A L N L E R Z L S L
Sample Output 3
3