← 返回题目列表

AtCoder · exawizards2019_c

C. 潜伏巫师

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

有 N 编号的方块 1 to N 从左到右。 每个方格上都写有一个字符,而方格 i 有一封信 s_i。此外,最初每个方格上都有一个傀儡。

潜伏演员 Q 移动傀儡的法术。

的 i-第一个咒语由两个字符组成 t_i 和 d_i,其中 d_i is L or R。 当 Snuke 施展此法术时,对于角色所在的每个方格 t_i,如果满足以下条件,该方格上的所有傀儡都会移动到左侧相邻的方格 d_i is L,并移动到右侧相邻的方块,如果 d_i is R.

然而,当傀儡试图从广场向左移动时 1 或从 Square 向右移动 N,它消失了。

找出 Snuke 施放后剩余的傀儡数量 Q 咒语。

约束

  • 1 \leq N,Q \leq 2 \times 10^{5}
  • |s| = N
  • s_i 和 t_i 为大写英文字母。
  • d_i is L or 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 尝试向左移动并消失。
  • 在第二个咒语中,广场上的傀儡 2 向左移动。
  • 在第三个咒语中,魔像没有移动。
  • 在第四个咒语中,广场上的傀儡 1 向右移动。
  • 施放四个法术后,广场上出现一个傀儡 2 和广场上的一个傀儡 3,总共剩下两个傀儡。

示例输入 2

8 3
AABCBDBA
A L
B R
A R

示例输出 2

5
  • 施展三个法术后,广场上出现一个傀儡 2,广场上的两个傀儡 4 和广场上的两个傀儡 6,总共剩下五个傀儡。
  • 请注意,单个法术可以移动多个傀儡。

示例输入 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