AT_abc322_f [ABC322F] Vacation Query

[problemUrl]: https://atcoder.jp/contests/abc322/tasks/abc322_f `0`, `1` からなる長さ $ N $ の文字列 $ S $ が与えられます。$ S $ の $ i $ 文字目を $ S_i $ とします。 $ Q $ 個のクエリを与えられた順に処理してください。 クエリは $ 3 $ 個の整数の組 $ (c,\ L,\ R) $ で表されて、$ c $ の値によってクエリの種類が異なります。 - $ c=1 $ のとき : $ L\ \leq\ i\ \leq\ R $ を満たす整数 $ i $ について、$ S_i $ が `1` ならば `0` に、`0` ならば `1` に変更する。 - $ c=2 $ のとき : $ S $ の $ L $ 文字目から $ R $ 文字目までを取り出して出来る文字列を $ T $ とする。$ T $ に含まれる連続する `1` の長さの最大値を出力する。

入力は以下の形式で標準入力から与えられる。ここで $ \mathrm{query}_i $ は $ i $ 番目のクエリを意味する。 > $ N $ $ Q $ $ S $ $ \mathrm{query}_1 $ $ \mathrm{query}_2 $ $ \vdots $ $ \mathrm{query}_Q $ 各クエリは次の形式で与えられる。 > $ c $ $ L $ $ R $

$ c=2 $ であるクエリの個数を $ k $ として、$ k $ 行出力せよ。 $ i $ 行目には $ i $ 番目の $ c=2 $ であるクエリに対する答えを出力せよ。

### 制約 - $ 1\ \leq\ N\ \leq\ 5\ \times\ 10^5 $ - $ 1\ \leq\ Q\ \leq\ 10^5 $ - $ S $ は長さ $ N $ の `0`, `1` からなる文字列 - $ c\ \in\ \lbrace\ 1,\ 2\ \rbrace $ - $ 1\ \leq\ L\ \leq\ R\ \leq\ N $ - $ N,\ Q,\ c,\ L,\ R $ は全て整数 ### Sample Explanation 1 クエリを順に処理すると次のようになります。 - はじめ、$ S= $ `1101110` です。 - $ 1 $ 番目のクエリについて、$ T\ = $ `1101110` です。$ T $ に含まれる連続する `1` の中で最も長いものは、$ T $ の $ 4 $ 文字目から $ 6 $ 文字目からなる `111` なので、答えは $ 3 $ になります。 - $ 2 $ 番目のクエリについて、$ T\ = $ `101` です。$ T $ に含まれる連続する `1` の中で最も長いものは、$ T $ の $ 1 $ 文字目あるいは $ 3 $ 文字目の `1` なので、答えは $ 1 $ になります。 - $ 3 $ 番目のクエリについて、操作後の $ S $ は `1110000` です。 - $ 4 $ 番目のクエリについて、$ T\ = $ `00` です。$ T $ に `1` は含まれないので答えは $ 0 $ になります。 - $ 5 $ 番目のクエリについて、操作後の $ S $ は `1111111` です。 - $ 6 $ 番目のクエリについて、$ T\ = $ `1111111` です。$ T $ に含まれる連続する `1` の中で最も長いものは、$ T $ の $ 1 $ 文字目から $ 7 $ 文字目からなる `1111111` なので、答えは $ 7 $ になります。