この問題はセグメント木 (Segment Tree) を用いて解くことが出来ますが、載せるもの (セグメント木の各要素) が複雑となるものの代表例です。

ACL のセグメント木 で定義する必要があるのは以下の \(3\) つです。

• 型 S … セグメント木の各要素の構造です。
• 二項演算 S op(S a, S b) … セグメント木上で横に並ぶ \(2\) つの区間 \([l,m), [m,r)\) を連結して \([l,r)\) に関する情報を得るための演算です。 \(a\) は区間 \([l,m)\) に、 \(b\) は区間 \([m,r)\) に対応します。
• 単位元 S e() … 「演算 op に関わっても何もしない」要素です。厳密には、全ての \(a \in S\) について op(a,e())=op(e(),a)=a が成り立つ必要があります。

区間 \([l,r)\) に対応する情報をひとつの型 S で持つことになります。このとき、例えば以下の情報を持つとうまくいきます。

• \([l,r)\) のうち最も左で連続している文字種 \(lefc\) とその長さ \(lefn\)
• \([l,r)\) のうち最も右で連続している文字種 \(rigc\) とその長さ \(rign\)
• 区間全体が同じ文字かどうかのフラグ \(con\)
  • \(con\) が真である場合、例えば aaaaa のような文字列に対応して全体がひとつの連続を成しているため、特別な取り扱いをする必要があります。
• 区間 \([l,r)\) だけを抜き出した際の同じ文字の連続の最大長 \(ans\)

例を挙げましょう。 yyzzzbba に対応する情報は \(lefc=\) y \(,lefn=2,rigc=\) a \(,rign=1,con=\) false \(,ans=3\) です。

また、長さ \(1\) の文字列に対応する S の要素も求めておく必要があります。(これは通常は簡単に求められるはずです。) これは実装例では cvrt という関数名で実装されています。

実装の詳細は以下の実装例を参照してください。
時間計算量は \(O(N+Q \log N)\) です。

実装例 (C++):

#include<bits/stdc++.h>
#include<atcoder/segtree>

using namespace std;
using namespace atcoder;

typedef struct{
  char lefc;
  int lefn;
  char rigc;
  int rign;
  bool con;
  int ans;
}S;

S e(){
  return {'*',0,'*',0,true,0};
}

S op(S l,S r){
  if(l.lefc=='*'){return r;}
  if(r.lefc=='*'){return l;}

  S res;
  res.ans=max(l.ans,r.ans);

  if(l.con && r.con){
    if(l.lefc==r.lefc){
      res.lefc=l.lefc;
      res.lefn=(l.lefn+r.lefn);
      res.con=true;
    }
    else{
      res.lefc=l.lefc;
      res.lefn=l.lefn;
      res.rigc=r.lefc;
      res.rign=r.lefn;
      res.con=false;
    }
  }
  else if(l.con){
    res.con=false;
    if(l.lefc==r.lefc){
      res.lefc=l.lefc;
      res.lefn=l.lefn+r.lefn;
    }
    else{
      res.lefc=l.lefc;
      res.lefn=l.lefn;
    }
    res.rigc=r.rigc;
    res.rign=r.rign;
  }
  else if(r.con){
    res.con=false;
    res.lefc=l.lefc;
    res.lefn=l.lefn;
    if(l.rigc==r.lefc){
      res.rigc=r.lefc;
      res.rign=l.rign+r.lefn;
    }
    else{
      res.rigc=r.lefc;
      res.rign=r.lefn;
    }
  }
  else{
    res.con=false;
    res.lefc=l.lefc;
    res.lefn=l.lefn;
    res.rigc=r.rigc;
    res.rign=r.rign;
    if(l.rigc==r.lefc){
      res.ans=max(res.ans,l.rign+r.lefn);
    }
  }

  res.ans=max(res.ans,max(res.lefn,res.rign));

  return res;
}

S cvrt(char c){
  return {c,1,'*',0,true,1};
}

int main(){
  int n,q;
  cin >> n >> q;
  string s;
  cin >> s;
  vector<S> ini(n);
  for(int i=0;i<n;i++){
    ini[i]=cvrt(s[i]);
  }
  segtree<S,op,e> seg(ini);
  while(q>0){
    q--;
    int typ;
    cin >> typ;
    if(typ==1){
      int i;
      char x;
      cin >> i >> x;
      seg.set(i-1,cvrt(x));
    }
    else{
      int l,r;
      cin >> l >> r;
      cout << seg.prod(l-1,r).ans << "\n";
    }
  }
  return 0;
}