この問題はクエリ問題です。よって、クエリを高速に処理するためにどのようなデータを持ってどのようにクエリを処理するかを考えていく必要があります。

まずはクエリを処理する方針を考えてみましょう。ある \((L, R)\) に対する答えが \(n\) だったとします。この時、

• 長さ \(n\) 以下の \(11/22\) 文字列は \(S\) の \(L\) 文字目から \(R\) 文字目からなる部分文字列に部分列として含まれて、
• 長さ \(n\) より大きい \(11/22\) 文字列は部分列として含まれない

ことが確認できます。このような単調性を利用すれば、次のような二分探索を用いる発想が浮かびます。

• はじめ \(l=-1, r=N+1\) とする。
• \(r - l \geq 1\) である間次の操作を行う。
  • \(m = \lfloor (l+r) / 2 \rfloor\) とする。
  • 長さ \(2m+1\) の \(11/22\) 文字列が部分列として区間内に存在するかを判定する。
  • 存在すれば \(l = m\) として、存在しなければ \(r = m\) とする。
• 操作後の \(l\) が \(-1\) である場合、\(11/22\) 文字列は部分列として区間内に存在しない。そうでない場合、長さ \(2l+1\) の \(11/22\) 文字列が部分列として存在して、これが最長である。

このアルゴリズムは正しく動作しますが、

• 長さ \(2m+1\) の \(11/22\) 文字列が部分列として区間内に存在するかを判定する。

という部分問題の解法がまだわかっていません。この部分問題が高速に解ければこの問題を \(\mathrm{O}(Q \log N \times (部分問題の計算量))\) で解くことが出来るので、部分問題を解くことを考えます。

この部分問題は適切な情報を前計算で計算しておけばそれを適宜参照することで解くことが出来ます。例えば

• \(v_1\) を \(S[i] =\) 1 であるような \(i\) からなる広義単調増加な列
• \(v_2\) を \(S[i] =\) 2 であるような \(i\) からなる広義単調増加な列
• \(v_3\) を \(S[i] =\) / であるような \(i\) からなる広義単調増加な列

を持っておくと、部分問題は適切な二分探索により \(\mathrm{O}(\log N)\) で解くことが出来ます。(詳細は実装例を参照してください) また、持つ情報を工夫することで部分問題を \(\mathrm{O}(1)\) で解くこともできます。

以上よりこの問題を \(\mathrm{O}(N + Q \log^2 N)\) あるいは \(\mathrm{O}(N + Q \log N)\) で解くことが出来て、これは十分高速です。

• 実装例(C++, \(\mathrm{O}(N + Q \log^2 N)\))

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int lb(const vector<int>& v, int x) {
  return lower_bound(begin(v), end(v), x) - begin(v);
}
int sz(const vector<int>& v) { return v.size(); }

int main() {
  int N, Q;
  string S;
  cin >> N >> Q >> S;

  vector<int> idx1, idx2, idxs;
  for (int i = 0; i < N; i++) {
    (S[i] == '1' ? idx1 : S[i] == '2' ? idx2 : idxs).push_back(i);
  }
  while (Q--) {
    int l, r;
    cin >> l >> r;
    --l;
    
    // 1, 2 の長さが len である 11/22 文字列が存在するか？
    auto f = [&](int len) -> bool {
      if (len == 0) {
        // / を発見
        int j = lb(idxs, l);
        if (j >= sz(idxs)) return false;
        return idxs[j] < r;
      }
      // 1 を発見
      int i = lb(idx1, l);
      if (i + len - 1 >= sz(idx1)) return false;
      // / を発見
      int j = lb(idxs, idx1[i + len - 1]);
      if (j >= sz(idxs)) return false;
      // 2 を発見
      int k = lb(idx2, idxs[j]);
      if (k + len - 1 >= sz(idx2)) return false;
      return idx2[k + len - 1] < r;
    };

    int ok = -1, ng = N + 1;
    while (ok + 1 < ng) {
      int m = (ok + ng) / 2;
      (f(m) ? ok : ng) = m;
    }
    cout << (ok == -1 ? 0 : ok * 2 + 1) << "\n";
  }
}