K - 最頻文字クエリ 解説 /

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

問題文

英小文字からなる長さ N の文字列 S が与えられます。

Q 個のクエリが与えられるので処理してください。クエリは 2 種類あり、以下のいずれかの形式で与えられます。

  • 1 p c : S の p 文字目を文字 c に置き換える。
  • 2 l r : S の l 文字目から r 文字目までに最も多く含まれる文字が何個含まれるかを出力する。

制約

  • 1\le N\le 2\times 10^5
  • 1\le Q\le 2\times 10^5
  • S は英小文字からなる長さ N の文字列
  • 1\le p\le N
  • c は英小文字
  • 1\le l\le r\le N

入力

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

N Q
S
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

各クエリ \text{query}_Q は以下の 2 種類のいずれかの形式で与えられる。

1 p c

2 l r

出力

問題文の指示に従ってクエリへの答えを改行区切りで出力せよ。

入力例 1

6 4
abbabc
2 1 3
2 1 6
1 5 d
2 1 6

出力例 1

2
3
2
  • S の 1 文字目から 3 文字目までは abb です。この中では b が最も多く含まれており、その出現回数は 2 回です。したがって、 1 つ目のクエリでは 2 を出力します。
  • S の 1 文字目から 6 文字目までは abbabc です。この中では b が最も多く含まれており、その出現回数は 3 回です。したがって、 3 つ目のクエリでは 3 を出力します。
  • 3 つ目のクエリでは S の 5 文字目を d に変更します。その結果、 S= abbadc となります。
  • S の 1 文字目から 6 文字目までは abbadc です。この中では a と b が最も多く含まれており、その出現回数は 2 回です。したがって、 4 つ目のクエリでは 2 を出力します。

入力例 2

8 4
nooutput
1 5 a
1 4 y
1 6 f
1 1 q

出力例 2














入力例 3
7 6
atcoder
2 1 7
1 1 r
2 1 7
1 2 r
2 1 7
1 4 r












出力例 3
1
2
3












Problem Statement
You are given a string S of length N, consisting of lowercase English letters.


Process the given Q queries.  There are two kinds of queries given as follows:


    

  • 1 p c: Set the p-th character of S to the character c.
    • 

  • 2 l r: Print how many times the most frequent letter occur, among the l-th through r-th characters of S.
    • 












Constraints
    

  • 1\le N\le 2\times 10^5
    • 

  • 1\le Q\le 2\times 10^5
    • 

  • S is a string of length N, consisting of lowercase English letters.
    • 

  • 1\le p\le N
    • 

  • c is a lowercase English letter.
    • 

  • 1\le l\le r\le N
    • 
















Input
The input is given from Standard Input in the following format:


N Q
S
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q



Each query \text{query}_Q is given in one of the following formats:


1 p c



2 l r












Output
Print the response to the queries asked in the problem statement, separated by newlines.















Sample Input 1
6 4
abbabc
2 1 3
2 1 6
1 5 d
2 1 6












Sample Output 1
2
3
2



    

  • The 1-st through 3-rd characters of S are abb.  Among them, b occurs most frequently, namely 2 times.  Thus, print 2 for the 1-st query.
    • 

  • The 1-st through 6-th characters of S are abbabc.  Among them, b occurs most frequently, namely 3 times.  Thus, print 3 for the 2-nd query.
    • 

  • For the 3-rd query, set the 5-th character of S to d, making S= abbadc.
    • 

  • The 1-st through 6-th characters of S are abbadc.  Among them, a and b occur most frequently, namely 2 times each.  Thus, print 2 for the 4-th query.
    • 














Sample Input 2
8 4
nooutput
1 5 a
1 4 y
1 6 f
1 1 q












Sample Output 2













Sample Input 3
7 6
atcoder
2 1 7
1 1 r
2 1 7
1 2 r
2 1 7
1 4 r












Sample Output 3
1
2
3