This problem can be solved with a segment tree, but is also a good exercise of it where the information to maintain (the contents of each node in the segment tree) is complex.

In ACL (AtCoder Library)’s segment tree, you need to define the following three:

• Type S: the structure of element of the segment tree.
• Binary operation S op(S a, S b): the operation to concatenate two adjacent segments \([l,m)\) and \([m,r)\) to obtain information for \([l,r)\). Here, \(a\) corresponds to \([l,m)\), and \(b\) to \([m,r)\).
• Identity element S e(): an element with which applying operation op results in nothing. Formally, op(a,e())=op(e(),a)=a should hold for all \(a \in S\).

We need to maintain the information for segment \([l,r]\) in a single type S. For example, it is sufficient to record the following:

• for the leftmost repetition of the same character within \([l,r)\), the repeated character \(lefc\) and its count \(lefn\)
• for the rightmost repetition of the same character within \([l,r)\), the repeated character \(rigc\) and its count \(rign\)
• a flag \(con\) representing whether all characters in the segment are the same
  • If \(con\) is true, for example in string aaaaa, the entire string forms a single segment, so we need to treat specially.
• the length of maximum consecutive repetition of the same character within the segment \([l,r)\).

For instance, for yyzzzbba we have \(lefc=\) y \(,lefn=2,rigc=\) a \(,rign=1,con=\) false \(,ans=3\).

We also need to find the element of type S for a length-\(1\) string. (This should be typically straightforward.) In the sample code, it is implemented as the function cvrt.

For more details, please refer to the sample code below.
The time complexity is \(O(N+Q \log N)\).

Sample code (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;
}