概要

各クエリ区間 \([L, R]\) の中で「隣り合う区画が同じ色になっている場所」の個数を、高速に答える問題です。隣接一致を配列化し、その累積和で区間和を求めます。

考察

求めたいのは、区間内の \(i\)（\(L \le i \le R-1\)）について \(C_i = C_{i+1}\) となる個数です。

素朴に各クエリごとに \(i=L\) から \(R-1\) まで調べると、1クエリあたり最大 \(O(N)\)、全体で最大 \(O(NQ)\) になります。制約は \(N,Q \le 2\times 10^5\) なので、最悪 \(4\times 10^{10}\) 回程度の比較になり、確実に時間切れです。

ここで重要な気づきは次の通りです：

• 「隣接が同じかどうか」は位置 \(i\) ごとに \(C_i\) と \(C_{i+1}\) を見れば一意に決まる
• よって、まず各 \(i\) に対してフラグ \(A_i = [C_i = C_{i+1}]\)（真なら1、偽なら0）を作れる
• 各クエリの答えは、結局 \(A_L + A_{L+1} + \cdots + A_{R-1}\) という区間和になる

区間和は累積和（prefix sum）を作っておけば \(O(1)\) で答えられます。

例： - \(C = [1,1,2,2,2]\) のとき
隣接一致フラグは \(A = [1,0,1,1]\)（(1,2),(2,3),(3,4),(4,5)の一致） - クエリ \([L,R]=[2,5]\) では \(i=2..4\) を見るので、\(A_2+A_3+A_4 = 0+1+1=2\)

アルゴリズム

1. 配列 \(C\) を読む。
2. 隣接一致フラグの累積和 pref を作る。
   • pref[i] を「先頭から位置 \(i\) まで（正確には隣接ペア \((1,2)\) から \((i,i+1)\) まで）の一致数」として持つようにする。
   • 実装では pref[0]=0 とし、\(i=1..N-1\) について
     pref[i] = pref[i-1] + (C[i-1]==C[i])
3. 各クエリ \([L,R]\) について、必要なのは \(i=L..R-1\) の一致数。
   • これは累積和で pref[R-1] - pref[L-1] で求まる。
   • （pref は0-index、入力の \(L,R\) は1-indexなので、この形になる）

計算量

• 時間計算量: 前処理 \(O(N)\)、各クエリ \(O(1)\) なので合計 \(O(N+Q)\)
• 空間計算量: 累積和配列などで \(O(N)\)

実装のポイント

• 添字のずれ（1-index と 0-index）に注意します。入力の \(L,R\) は1-indexですが、Pythonの配列 C は0-indexです。

• pref[R-1] - pref[L-1] が「\([L, R-1]\) のフラグ和」になるように pref を定義している点が肝です。

• \(N,Q\) が大きいので、sys.stdin.buffer.read() による高速入力を使うと安定します。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    Q = next(it)
    C = [next(it) for _ in range(N)]

    pref = [0] * N  # pref[i] = sum of equal-adjacent flags up to position i (1-based for flags)
    for i in range(1, N):
        pref[i] = pref[i - 1] + (1 if C[i - 1] == C[i] else 0)

    out_lines = []
    for _ in range(Q):
        L = next(it)
        R = next(it)
        # count flags in [L, R-1] => pref[R-1] - pref[L-1]
        out_lines.append(str(pref[R - 1] - pref[L - 1]))

    sys.stdout.write("\n".join(out_lines))

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。