103722: [Atcoder]ABC372 C - Count ABC Again
Description
Score : $350$ points
Problem Statement
You are given a string $S$ of length $N$. You are also given $Q$ queries, which you should process in order.
The $i$-th query is as follows:
- Given an integer $X_i$ and a character $C_i$, replace the $X_i$-th character of $S$ with $C_i$. Then, print the number of times the string
ABC
appears as a substring in $S$.
Here, a substring of $S$ is a string obtained by deleting zero or more characters from the beginning and zero or more characters from the end of $S$.
For example, ab
is a substring of abc
, but ac
is not a substring of abc
.
Constraints
- $3 \le N \le 2 \times 10^5$
- $1 \le Q \le 2 \times 10^5$
- $S$ is a string of length $N$ consisting of uppercase English letters.
- $1 \le X_i \le N$
- $C_i$ is an uppercase English letter.
Input
The input is given from Standard Input in the following format:
$N$ $Q$ $S$ $X_1$ $C_1$ $X_2$ $C_2$ $\vdots$ $X_Q$ $C_Q$
Output
Print $Q$ lines. The $i$-th line $(1 \le i \le Q)$ should contain the answer to the $i$-th query.
Sample Input 1
7 4 ABCDABC 4 B 3 A 5 C 4 G
Sample Output 1
2 1 1 0
After processing each query, $S$ becomes as follows.
- After the first query: $S=$
ABCBABC
. In this string,ABC
appears twice as a substring. - After the second query: $S=$
ABABABC
. In this string,ABC
appears once as a substring. - After the third query: $S=$
ABABCBC
. In this string,ABC
appears once as a substring. - After the fourth query: $S=$
ABAGCBC
. In this string,ABC
appears zero times as a substring.
Sample Input 2
3 3 ABC 1 A 2 B 3 C
Sample Output 2
1 1 1
There are cases where $S$ does not change through processing a query.
Sample Input 3
15 10 BBCCBCACCBACACA 9 C 11 B 5 B 11 B 4 A 8 C 8 B 5 B 7 B 14 B
Sample Output 3
0 0 0 0 1 1 2 2 1 1
Output
得分:$350$分
问题陈述
给你一个长度为$N$的字符串$S$。还给你$Q$个查询,你应该按顺序处理它们。
第$i$个查询如下:
- 给定一个整数$X_i$和一个字符$C_i$,将字符串$S$中的第$X_i$个字符替换为$C_i$。然后,打印字符串
ABC
作为子字符串在$S$中出现的次数。
在这里,$S$的子字符串是通过从$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