← 返回题目列表

AtCoder · abc372_c

F. 再数一遍ABC

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

分数: 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