1522 - Douteki Programming

時間制限 2 秒 / メモリ制限 128 MB / 得点 5 / Writer ei1903 / x 1 / 統計 /

TLE
2sec
MLE
128MB
得点
5

問題

文字列$ \ S \ $について 1165 - ハッピー文字列YDK の答えを返す関数を$ \ YDK(S) \ $とする。すなわち、$ \ YDK($YDKYDK$) \ = 4 \ $である。

あなたは長さ$ \ N \ $の文字列$ \ S \ $を所持しており、この文字列に対して以下のような更新クエリが$ \ Q \ $回にわたって与えられる。各更新後の文字列$ \ S \ $について、$YDK(S) \ $を求めよ。

$i \ $回目のクエリでは整数$ \ l_i,r_i \ $及び文字$ \ c_i \ $が与えられ、意味は次の通りである。

  • $S \ $の$ \ l_i \ $文字目から$ \ r_i \ $文字目までを文字$ \ c_i \ $に置き換える。

入力

入力は以下の形式で標準入力から与えられる。

$N \ Q$
$S$
$l_1 \ r_1 \ c_1$
$l_2 \ r_2 \ c_2$
$\vdots$
$l_Q \ r_Q \ c_Q$

出力

出力は$ \ Q \ $行からなり、$i \ $行目には$ \ i \ $番目までの更新を行った後の文字列$ \ S \ $について$ \ YDK(S) \ $を出力せよ。

制約

全ての入出力ケースについて以下を満たす。

  • $1 \leq N,Q \leq 2 \times 10^5$
  • $S \ $は英大文字のみからなる長さ$ \ N \ $の文字列
  • $1 \leq l_i \leq r_i \leq N$
  • $c_i \ $は英大文字

入出力例

入力例1

6 3
YYDDDD
5 6 K
1 4 Y
5 5 D

出力例1

8
0
4
  • 1回目:$ \ S = $YYDDKK なので8
  • 2回目:$ \ S = $YYYYKK なので0
  • 3回目:$ \ S = $YYYYDK なので4

入力例2

8 5
YDKKDYKK
4 8 C
6 8 K
7 7 D
2 5 Y
3 4 N

出力例2

1
4
4
5
3