B - 電光掲示板の更新 解説 /

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

配点 : 333 点

問題文

横一列に N 個のマスが並んだ電光掲示板があります。各マスには英大文字 1 文字が表示されており、左から i 番目のマスに表示されている文字を S_i とすると、初期状態は長さ N の文字列 S = S_1 S_2 \dots S_N で表されます。

高橋君はこの掲示板に対して Q 回の 更新 を順に行います。k 回目の更新では、左から i_k 番目のマスの文字を英大文字 c_k に変更します（現在の文字と同じ文字に変更する場合もあります）。

1 \le i < N を満たす整数 i に対して、左から i 番目のマスと i+1 番目のマスに表示されている文字が同じであるとき、この組を 一致ペア と呼びます。一致ペアの個数とは、この条件を満たす i の個数のことです。

各更新の直後について、一致ペアの個数を求めてください。

制約

  • 2 \leq N \leq 10^6
  • 1 \leq Q \leq 10^5
  • S は長さ N の英大文字からなる文字列
  • 1 \leq i_k \leq N (1 \leq k \leq Q)
  • c_k は英大文字 (1 \leq k \leq Q)
  • N, Q, i_k は整数

入力

N Q
S
i_1 c_1
i_2 c_2
\vdots
i_Q c_Q
  • 1 行目には、マスの個数 N と更新回数 Q がスペース区切りで与えられる。
  • 2 行目には、初期状態の文字列 S が与えられる。S の i 文字目が、左から i 番目のマスに表示されている文字を表す。
  • 3 行目以降の Q 行には、各更新の内容が与えられる。このうち k 行目（全体では 2 + k 行目）には、k 回目の更新で変更するマスの位置 i_k と変更後の文字 c_k がスペース区切りで与えられる。

出力

Q 行出力せよ。k 行目には、k 回目の更新直後における一致ペアの個数を出力せよ。

入力例 1

5 4
ABBCC
2 A
3 A
5 D
4 D

出力例 1

2
3
2
3

入力例 2

6 5
ABCDEF
1 A
2 A
6 E
5 E
3 A

出力例 2

0
1
2
2
3

入力例 3

12 8
AABCCDDEFGGH
3 A
4 A
5 A
8 D
9 D
10 D
11 D
12 D

出力例 3

5
5
6
7
8
8
9
10

入力例 4

20 12
ABBAACCDDDEEFFGGHHII
1 B
4 B
5 B
10 E
8 C
9 C
20 H
19 H
12 F
11 F
15 H
16 H

出力例 4

11
11
12
12
12
13
12
14
14
14
13
15

入力例 5

2 1
AA
1 B

出力例 5

0

Score : 333 pts

Problem Statement

There is an electronic display board with N cells arranged in a horizontal row. Each cell displays a single uppercase English letter. Let S_i denote the character displayed in the i-th cell from the left. The initial state is represented by a string S = S_1 S_2 \dots S_N of length N.

Takahashi performs Q updates on this display board in order. In the k-th update, he changes the character in the i_k-th cell from the left to the uppercase English letter c_k (the character may be changed to the same character as the current one).

For an integer i satisfying 1 \le i < N, if the characters displayed in the i-th cell and the (i+1)-th cell from the left are the same, this pair is called a matching pair. The number of matching pairs is the number of such i that satisfy this condition.

For each update, determine the number of matching pairs immediately after the update.

Constraints

  • 2 \leq N \leq 10^6
  • 1 \leq Q \leq 10^5
  • S is a string of length N consisting of uppercase English letters
  • 1 \leq i_k \leq N (1 \leq k \leq Q)
  • c_k is an uppercase English letter (1 \leq k \leq Q)
  • N, Q, i_k are integers

Input

N Q
S
i_1 c_1
i_2 c_2
\vdots
i_Q c_Q
  • The first line contains the number of cells N and the number of updates Q, separated by a space.
  • The second line contains the initial string S. The i-th character of S represents the character displayed in the i-th cell from the left.
  • The following Q lines contain the details of each update. The k-th of these lines (the (2 + k)-th line overall) contains the position i_k of the cell to be changed in the k-th update and the new character c_k, separated by a space.

Output

Output Q lines. The k-th line should contain the number of matching pairs immediately after the k-th update.

Sample Input 1

5 4
ABBCC
2 A
3 A
5 D
4 D

Sample Output 1

2
3
2
3

Sample Input 2

6 5
ABCDEF
1 A
2 A
6 E
5 E
3 A

Sample Output 2

0
1
2
2
3

Sample Input 3

12 8
AABCCDDEFGGH
3 A
4 A
5 A
8 D
9 D
10 D
11 D
12 D

Sample Output 3

5
5
6
7
8
8
9
10

Sample Input 4

20 12
ABBAACCDDDEEFFGGHHII
1 B
4 B
5 B
10 E
8 C
9 C
20 H
19 H
12 F
11 F
15 H
16 H

Sample Output 4

11
11
12
12
12
13
12
14
14
14
13
15

Sample Input 5

2 1
AA
1 B

Sample Output 5

0