はじめに、以下の情報を計算しておきます。

\(f_i = \) ( \(C_{i-1}=C_i\) なら \(1\) 、そうでないなら \(0\) )
なお、便宜上 \(f_1=0\) としておきます。
この上で、 \(s_i\) を \(f_i\) の累積和、すなわち \(s_i = \sum_{k=1}^{i} f_i\) とします。

すると、質問 \(L,R\) に対して答えは \(s_R-s_L\) となります。
これは、以下の理由で説明できます。

• \(s_R\) が \(2 \le i \le R\) について \(C_{i-1}=C_i\) となっている箇所の個数を表す。
• \(s_L\) が \(2 \le i \le L\) について \(C_{i-1}=C_i\) となっている箇所の個数を表す。
• \(s_R-s_L\) とする、つまり上記の差分を取ることで、 \(L+1 \le i \le R\) について \(C_{i-1} = C_i\) となっている箇所の個数を求めることができる。

この解法の時間計算量は \(O(N+Q)\) 、空間計算量は \(O(N)\) です。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int N,Q;
  cin >> N >> Q;
  vector<int> C(N+1);
  for(int i=1;i<=N;i++){
    cin >> C[i];
  }
  vector<int> s(N+1,0);
  for(int i=2;i<=N;i++){
    s[i]=s[i-1];
    if(C[i-1]==C[i]){s[i]++;}
  }
  while(Q--){
    int L,R;
    cin >> L >> R;
    cout << s[R]-s[L] << "\n";
  }
  return 0;
}