各質問ごとに対象の部分文字列 \(S_{l_i}S_{l_i+1}\ldots S_{r_i}\) を走査して同じ英小文字が隣接する箇所の個数を愚直に数える方法では、 \(1\) つの質問に答えるのに最悪で \(\Theta(N)\) 時間かかり、\(Q\) 個の質問全体では最悪で \(\Theta(QN)\) 時間かかるため、 実行制限時間に間に合わせることは絶望的です。

そこで、各質問に高速に答える方法を以下で考えます。 質問対象の部分文字列を \(S_{l}S_{l+1}\ldots S_{r}\) とおき、この質問に高速に答える方法を以下で考えましょう。

入力で与えられた文字列 \(S\) に対し、長さ \(N-1\) の数列 \(A = (A_1, A_2, \ldots, A_{N-1})\) を、

\[A_i = \begin{cases} 1 &\text{if} \,\,S_i = S_{i+1}\\ 0 &\text{if}\,\, S_i \neq S_{i+1} \end{cases}\]

で定めると、質問の答えは \(A_{l} + A_{l+1} + \cdots + A_{r-1}\) と表せます。 さらに、数列 \(B = (B_0, B_1, B_2, \ldots, B_{N-1})\) を、

\[B_i = \begin{cases} 0 &\text{if} \,\,i = 0\\ A_1 + A_2 + \cdots + A_i &\text{if}\,\, i \geq 1 \end{cases}\]

で定めます。つまり、\(B\) は \(A\) の先頭からの累積和の数列です。 このとき、質問の答え \(A_{l} + A_{l+1} + \cdots + A_{r-1} \)は、

\[A_{l} + A_{l+1} + \cdots + A_{r-1} = (A_1 + A_2 + \cdots + A_{r-1}) - (A_1 + A_2 + \cdots + A_{l-1}) = B_{r-1} - B_{l-1}\]

と、数列 \(B\) の \(2\) つの要素の差 \(B_{r-1} - B_{l-1}\) で表せます。 したがって、あらかじめ数列 \(B\) が計算されていれば、各質問の答えは \(B_{r-1} - B_{l-1}\) を計算するだけで \(O(1)\) 時間で求められます。

したがって、

• まず、入力で与えられた文字列 \(S\) に対して、数列 \(A\) およびその累積和 \(B\) を前計算しておき、
• その後、各質問の答え \(B_{r_i-1} - B_{l_i-1}\) を各質問 \(O(1)\) 時間で求める

ことによって、全体で \(O(N+Q)\) 時間で本問題を解くことができます。 なお、数列 \(A\) から数列 \(B\) を求めるのは、数列 \(B\) が満たす漸化式

\[B_i = \begin{cases} 0 &\text{if} \,\,i = 0\\ B_{i-1} + A_i &\text{if}\,\, i \geq 1 \end{cases}\]

を用いて、\(O(N)\) 時間で可能です。

以下に、C++ 言語による本問題の正解例を記載します。

#include <iostream>
using namespace std;

int n, q;
char s[300001];
int a[300000], b[300000];

int main(void)
{
  cin >> n >> q;
  for(int i = 1; i <= n; i++) cin >> s[i];
  
  for(int i = 1; i <= n-1; i++) if(s[i] == s[i+1]) a[i] = 1;
  for(int i = 1; i <= n-1; i++) b[i] = b[i-1] + a[i];
  
  int l, r;
  for(int i = 1; i <= q; i++){
    cin >> l >> r;
    cout << b[r-1]-b[l-1] << "\n";
  }
  
  return 0;
}