\(\def \set #1#2{\{ #1 \ \vert \ #2 \}}\) \(\def \ra {\rightarrow}\)
解法
(交わらない)隣の二つの区間 \(I,J\) を結合したときを考える． 基本的には，\(I,J\) それぞれの 1 の連続区間の最大が \(I \cup J\) における最大となる．
しかし，結合したときに \(I\) の右端から伸びる連続する 1の区間と， \(J\) の左端から伸びる連続する 1の区間が結合するため， これが最大になる場合がある． また，区間全体が 1のときも注意が必要．
クエリ 1 により，0と 1を反転させるので，同様に \(I\) の左(右)から伸びる連続 0の区間の長さも持っておく． これらの情報を区間毎にもっておけば，lazy segtree で計算が出来る．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
struct D{
ll ma, l, r;
D(){
ma = 0, l = 0, r = 0; // [*]
}
};
struct S{
ll len;
D d[2];
S(){
// len = 0 も書いた方が安全な気はする．
// 書いてなくても ACしたけど．
}
S(bool c){
len = 1;
d[c].l = 1;
d[c].r = 1;
d[c].ma = 1;
// rem: c^1 の初期化も忘れない
// [*] において，Dのコンストラクタで初期化しているなら，
// 以下は書かなくても OK.
// d[c^1].l = 0;
// d[c^1].r = 0;
// d[c^1].ma = 0;
}
void show(string name = ""){
cout << name << endl;
cout << "len : " << len << endl;
rep(i,2){
cout << "i : " << i << endl;
cout << "d[i].ma : " << d[i].ma << endl;
cout << "d[i].l : " << d[i].l << endl;
cout << "d[i].r : " << d[i].r << endl;
}
cout << endl;
}
};
S op(S a, S b){
S c;
c.len = a.len + b.len;
rep(i,2) c.d[i].l = a.len != a.d[i].l ? a.d[i].l : (a.len + b.d[i].l);
rep(i,2) c.d[i].r = b.len != b.d[i].r ? b.d[i].r : (a.d[i].r + b.len);
rep(i,2) c.d[i].ma = max(a.d[i].ma, max(b.d[i].ma, a.d[i].r + b.d[i].l));
return c;
}
S e(){
S c;
rep(i,2) c.d[i].ma = 0;
rep(i,2) c.d[i].l = 0;
rep(i,2) c.d[i].r = 0;
c.len = 0;
return c;
}
using F = bool;
S mapping(F f, S x){
if(f) swap(x.d[0], x.d[1]);
return x;
}
F composition(F f, F g){
return f^g;
}
F id(){
return false;
}
int main() {
ll n,q;
cin >> n >> q;
string s; cin >> s;
lazy_segtree<S,op,e,F,mapping,composition,id> t(n);
rep(i,n){
t.set(i, S(s[i]-'0'));
}
rep(qi,q){
ll c; cin >> c;
ll l,r; cin >> l >> r;
--l;
if(c == 1){
t.apply(l,r,true);
}else{
cout << t.prod(l,r).d[1].ma << endl;
}
}
return 0;
}
