F - Max Combo Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MiB

配点 : 525 点

問題文

長さ N の英小文字からなる文字列 S があります。以下のクエリを全部で Q 個処理してください。

  • タイプ 1 : S の i 文字目を x に変更する。
  • タイプ 2 : 現時点の S の l 文字目から r 文字目までを抜き出した文字列を t とする。この文字列に対して次のように定義される f(t) を求めよ。
    • f(t) は t 中の同じ文字の連続の最大長である。
    • 厳密には、 1 \le a \le b \le |t| かつ t の a 文字目から b 文字目までが全て等しいような整数 a,b を選ぶとき、 f(t) は b-a+1 の値としてありうる最大値である。
    • 例えば f( aaaccbbbb )=4 、 f( bbaaabb )=3 、 f( x )=1 である。

制約

  • N は 1 以上 5 \times 10^5 以下の整数
  • S は英小文字からなる長さ N の文字列
  • Q は 1 以上 5 \times 10^5 以下の整数
  • タイプ 1 のクエリは以下の制約を満たす
    • i は 1 以上 N 以下の整数
    • x は英小文字
  • タイプ 2 のクエリは以下の制約を満たす
    • l,r は 1 \le l \le r \le N を満たす整数

入力

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

N Q
S
\rm{Query}_1
\rm{Query}_2
\vdots
\rm{Query}_Q

但し、 \rm{Query}_i は i 個目のクエリを表す。

タイプ 1 のクエリは以下の形式で与えられる。

1 i x

タイプ 2 のクエリは以下の形式で与えられる。

2 l r

出力

タイプ 2 のクエリが現れる度に、その解答を 1 行に出力せよ。
なお、入出力が大きくなる場合があるので、高速な方法で入出力を行うことを推奨する。

入力例 1

10 5
babaacczcc
2 1 4
1 3 a
2 1 10
1 8 c
2 1 10

出力例 1

1
4
5

この入力には 5 個のクエリが含まれます。

  • はじめ、文字列 S は babaacczcc です。
  • 1 番目のクエリはタイプ 2 で、 l=1,r=4 です。
    • 抜き出した文字列は baba であり、 f( baba )=1 です。
  • 2 番目のクエリはタイプ 1 で、 i=3,x= a です。
    • 変更後の文字列 S= baaaacczcc です。
  • 3 番目のクエリはタイプ 2 で、 l=1,r=10 です。
    • 抜き出した文字列は baaaacczcc であり、 f( baaaacczcc )=4 です。
  • 4 番目のクエリはタイプ 1 で、 i=8,x= c です。
    • 変更後の文字列 S= baaaaccccc です。
  • 5 番目のクエリはタイプ 2 で、 l=1,r=10 です。
    • 抜き出した文字列は baaaaccccc であり、 f( baaaaccccc )=5 です。

入力例 2

1 1
a
1 1 z

出力例 2



出力が空である場合もあります。






Score : 525 points







Problem Statement
There is a string S of length N consisting of lowercase English letters. Process a total of Q queries as follows:


    

  • Type 1 : Change the i-th character of S to x.
    • 

  • Type 2 : Let t be the substring of the current S from the l-th character through the r-th character. Find f(t) defined as follows for this string:
      

    • f(t) is the maximum length of consecutive identical characters in t.
      • 

    • More precisely, when choosing integers a,b such that 1 \le a \le b \le |t| and all characters from the a-th through the b-th character of t are equal, f(t) is the maximum possible value of b-a+1.
      • 

    • For example, f( aaaccbbbb )=4, f( bbaaabb )=3, f( x )=1.
      • 

    

    • 












Constraints
    

  • N is an integer between 1 and 5 \times 10^5, inclusive.
    • 

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

  • Q is an integer between 1 and 5 \times 10^5, inclusive.
    • 

  • Type 1 queries satisfy the following constraints:
      

    • i is an integer between 1 and N, inclusive.
      • 

    • x is a lowercase English letter.
      • 

    

    • 

  • Type 2 queries satisfy the following constraints:
      

    • l,r are integers satisfying 1 \le l \le r \le N.
      • 

    

    • 
















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


N Q
S
\rm{Query}_1
\rm{Query}_2
\vdots
\rm{Query}_Q



Here, \rm{Query}_i represents the i-th query.


Type 1 queries are given in the following format:


1 i x



Type 2 queries are given in the following format:


2 l r












Output
Every time a type 2 query appears, output the answer on one line.

The use of fast input and output methods is recommended because of potentially large input and output.















Sample Input 1
10 5
babaacczcc
2 1 4
1 3 a
2 1 10
1 8 c
2 1 10












Sample Output 1
1
4
5



This input contains five queries.


    

  • Initially, the string S is babaacczcc.
    • 

  • The 1st query is type 2 with l=1,r=4.
      

    • The extracted string is baba, and f( baba )=1.
      • 

    

    • 

  • The 2nd query is type 1 with i=3,x= a.
      

    • The string S after the change is baaaacczcc.
      • 

    

    • 

  • The 3rd query is type 2 with l=1,r=10.
      

    • The extracted string is baaaacczcc, and f( baaaacczcc )=4.
      • 

    

    • 

  • The 4th query is type 1 with i=8,x= c.
      

    • The string S after the change is baaaaccccc.
      • 

    

    • 

  • The 5th query is type 2 with l=1,r=10.
      

    • The extracted string is baaaaccccc, and f( baaaaccccc )=5.
      • 

    

    • 














Sample Input 2
1 1
a
1 1 z












Sample Output 2


The output may be empty.