以下、 \(Q=1,L=1,R=|S|\) として説明します。クエリでもやることは同じです。

まず、 / の位置を全てリストアップします。
その上で、 / のリストに対して以下の二分探索が成立します。

• ある / の左側にある \(1\) の数を \(C_1\) 、右側にある \(2\) の数を \(C_2\) とする。
• もし \(C_1 > C_2\) であれば、より左にある / を探索すべきである。
• そうでないなら、より右にある / を探索すべきである。

なぜなら、 \(C_1,C_2\) のうち大きくない方がボトルネックになっており、それを増やさない限り解は改善しないからです。

これらの操作は累積和や二分探索で実装することができ、全体で時間計算量 \(O(N + Q \log N)\) でこの問題に正解できます。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int lb(int x,vector<int> &a){
  int l=0,r=((int)a.size())-1;
  while(l<=r){
    int te=(l+r)/2;
    if(a[te]<x){l=te+1;}
    else{r=te-1;}
  }
  return l;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n,q;
  cin >> n >> q;
  string s;
  cin >> s;
  vector<int> c1(n+1,0);
  vector<int> c2(n+1,0);
  vector<int> sl;
  for(int i=0;i<n;i++){
    c1[i+1]=c1[i];
    c2[i+1]=c2[i];
    if(s[i]=='1'){
      c1[i+1]++;
    }
    else if(s[i]=='2'){
      c2[i+1]++;
    }
    else{
      sl.push_back(i+1);
    }
  }
  // for(auto &nx : c1){
  //   cout << nx << " ";
  // }cout << "\n";
  // for(auto &nx : c2){
  //   cout << nx << " ";
  // }cout << "\n";
  // for(auto &nx : sl){
  //   cout << nx << " ";
  // }cout << "\n";

  while(q>0){
    q--;
    int l,r;
    cin >> l >> r;
    int lef=lb(l,sl);
    int rig=lb(r+1,sl);
    if(lef==rig){
      cout << "0\n";
      continue;
    }
    rig--;

    int res=0;
    while(lef<=rig){
      int te=(lef+rig)/2;
      int pt=sl[te];

      int l1=(c1[pt]-c1[l-1]);
      int r2=(c2[r]-c2[pt]);

      res=max(res,2*min(l1,r2)+1);

      if(l1>r2){rig=te-1;}
      else{lef=te+1;}
    }
    cout << res << "\n";
  }
  return 0;
}