分数: 350 点
问题陈述
给你一个字符串 S 长度 N。还给你 Q 查询,您应按顺序处理。
的 树的 i第查询如下:
- 给定一个整数 X_i 和一个角色 C_i,替换 X_i- 第一个字符 S 与 C_i。然后,打印字符串出现的次数
ABC作为子字符串出现在 S.
这里,一个 子字符串 of S 是从开头删除零个或多个字符,从结尾删除零个或多个字符得到的字符串 S.
例如, ab 是一个子串 abc,但是 ac 不是以下的子串 abc.
约束
- 3 \le N \le 2 \times 10^5
- 1 \le Q \le 2 \times 10^5
- S 是一个长度为的字符串 N 由大写英文字母组成。
- 1 \le X_i \le N
- C_i 是一个大写英文字母。
输入
输入由标准输入按以下格式给出:
N Q S X_1 C_1 X_2 C_2 \vdots X_Q C_Q
输出
打印 Q 行。 的 i第行 (1 \le i \le Q) 应包含以下问题的答案 i- 第一个查询。
示例输入 1
7 4 ABCDABC 4 B 3 A 5 C 4 G
示例输出 1
2 1 1 0
处理每个查询后, S 变为如下。
- 第一次查询后: S=
ABCBABC。在这个字符串中,ABC作为子字符串出现两次。 - 第二次查询后: S=
ABABABC。在这个字符串中,ABC作为子字符串出现一次。 - 第三次查询后: S=
ABABCBC。在这个字符串中,ABC作为子字符串出现一次。 - 第四次查询后: S=
ABAGCBC。在这个字符串中,ABC作为子字符串出现零次。
示例输入 2
3 3 ABC 1 A 2 B 3 C
示例输出 2
1 1 1
在某些情况下 S 不会通过处理查询而改变。
示例输入 3
15 10 BBCCBCACCBACACA 9 C 11 B 5 B 11 B 4 A 8 C 8 B 5 B 7 B 14 B
示例输出 3
0 0 0 0 1 1 2 2 1 1