AT_abc381_e [ABC381E] 11/22 Subsequence

[problemUrl]: https://atcoder.jp/contests/abc381/tasks/abc381_e > この問題における 11/22 文字列の定義は A 問題および C 問題と同じです。 文字列 $ T $ が以下の条件を全て満たすとき、$ T $ を **11/22 文字列** と呼びます。 - $ |T| $ は奇数である。ここで、$ |T| $ は $ T $ の長さを表す。 - $ 1 $ 文字目から $ \frac{|T|+1}{2}\ -\ 1 $ 文字目までが `1` である。 - $ \frac{|T|+1}{2} $ 文字目が `/` である。 - $ \frac{|T|+1}{2}\ +\ 1 $ 文字目から $ |T| $ 文字目までが `2` である。 例えば `11/22`, `111/222`, `/` は 11/22 文字列ですが、`1122`, `1/22`, `11/2222`, `22/11`, `//2/2/211` はそうではありません。 `1`, `2`, `/` からなる長さ $ N $ の文字列 $ S $ が与えられるので、$ Q $ 個のクエリを処理してください。 各クエリでは $ L $, $ R $ が与えられます。$ S $ の $ L $ 文字目から $ R $ 文字目までからなる **(連続な)** 部分文字列を $ T $ としたとき、 11/22 文字列であるような $ T $ の **(連続とは限らない)** 部分列の長さの最大値を求めてください。そのような部分列が存在しないときは `0` を出力してください。

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

$ Q $ 行出力せよ。$ i $ 行目には $ i $ 番目のクエリへの答えを出力せよ。

### 制約 - $ 1\ \leq\ N\ \leq\ 10^5 $ - $ 1\ \leq\ Q\ \leq\ 10^5 $ - $ S $ は `1`, `2`, `/` からなる長さ $ N $ の文字列 - $ 1\ \leq\ L\ \leq\ R\ \leq\ N $ - $ N,\ Q,\ L,\ R $ は整数 ### Sample Explanation 1 $ 1 $ 番目のクエリについて、$ S $ の $ 1 $ 文字目から $ 7 $ 文字目からなる部分文字列は `111/212` です。この文字列は `11/22` を部分列として含み、これは 11/22 文字列であるような部分列として最大です。よって答えは $ 5 $ です。 $ 2 $ 番目のクエリについて、$ S $ の $ 9 $ 文字目から $ 12 $ 文字目からなる部分文字列は `1122` です。この文字列は 11/22 文字列であるような部分列を含まないので、答えは $ 0 $ です。