006 - HOJ-Substrings

時間制限 2 秒 / メモリ制限 1024 MB / 得点 500 / x 1 /


TLE
2sec
MLE
1024MB
得点
500

問題

レベル$ \ k \ $のHOJ文字列を、文字H,O,Jをこの順に$ \ k \ $個ずつ繋げた文字列と定義します。なお、レベル$ \ 0 \ $のHOJ文字列は空文字列です。

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

  • クエリ1:1 p c:$S \ $の$ \ p \ $文字目を文字$ \ c \ $に変更する。
  • クエリ2:2 l r:$S \ $の$ \ l \ $文字目から$ \ r \ $文字目までを$ \ S[l:r] \ $としたとき、$S[l:r] \ $の部分文字列であるようなHOJ文字列のレベルの最大値を出力する。

入力

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

$N \ Q$
$S$
$Query_1$
$Query_2$
$\vdots$
$Query_Q$

各クエリは以下のいずれかの形式で与えられる。

$1 \ p \ c$
$2 \ l \ r$

出力

クエリ2についての答えを改行区切りで出力せよ。

制約

  • $1 \leq N,Q \leq 3 \times 10^5$
  • $S \ $はH,O,Jのみからなる長さ$ \ N \ $の文字列
  • $1 \leq p \leq N$
  • $c \in \{$H,O,J$\}$
  • $1 \leq l \leq r \leq N$

入出力例

入力例

10 5
HOHOOJOJJJ
2 1 10
2 3 7
2 2 3
1 2 H
2 1 10

出力例

2
1
0
3
  1. HOHOOJOJJJにはレベル$ \ 2 \ $のHOJ文字列HHOOJJが部分文字列として含まれます。
  2. HOOJOにはレベル$ \ 1 \ $のHOJ文字列HOJが部分文字列として含まれます。
  3. OHにはレベル$ \ 0 \ $のHOJ文字列である空文字列が部分文字列として含まれます。
  4. $S \ $の$ \ 2 \ $文字目がHとなり$S = $HHHOOJOJJJとなります。
  5. HHHOOJOJJJにはレベル$ \ 3 \ $のHOJ文字列HHHOOOJJJが部分文字列として含まれます。