C - Count ABC Again 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 350 点

問題文

長さ N の文字列 S が与えられます。クエリが Q 個与えられるので、順番に処理してください。

i 番目のクエリは以下の通りです。

  • 整数 X_i と文字 C_i が与えられるので、 S の X_i 番目の文字を C_i に置き換える。その後、 S に文字列 ABC が部分文字列として何箇所含まれるかを出力する。

ここで、 S の 部分文字列 とは、S の先頭から 0 文字以上、末尾から 0 文字以上削除して得られる文字列のことをいいます。
例えば、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 は次のようになります。

  • 1 つ目のクエリを処理後： S= ABCBABC となる。この中に ABC は部分文字列として 2 回登場する。
  • 2 つ目のクエリを処理後： S= ABABABC となる。この中に ABC は部分文字列として 1 回登場する。
  • 3 つ目のクエリを処理後： S= ABABCBC となる。この中に ABC は部分文字列として 1 回登場する。
  • 4 つ目のクエリを処理後： S= ABAGCBC となる。この中に ABC は部分文字列として 0 回登場する。

入力例 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

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