概要

一列に並んだ花壇の各区画の色が与えられ、指定された区間内で隣接する同じ色の区画のペアの数を求めるクエリに答える問題。

考察

この問題では、各区間ごとに「隣り合う区画の色が同じかどうか」を判定し、その個数を求めることになります。

素朴な方法として、各クエリごとに範囲 \([L_j, R_j]\) 内の隣接ペアを一つずつ見ていく方法があります。しかし、この方法では各クエリに最悪 \(O(N)\) かかり、全体で \(O(Q \cdot N)\) となり、制約が \(N, Q \leq 2 \times 10^5\) なので時間内に処理できません（TLE）。

そこで、前処理によって各位置で「隣り合う区画の色が同じかどうか」を事前に計算しておきます。具体的には、長さ \(N\) の配列 same を用意し、same[i] = 1 を \(C[i] = C[i+1]\) のとき、そうでないときは 0 とします。

さらに、この same 配列の累積和を取っておくことで、任意の区間 \([L, R)\) における同じ色のペアの個数を \(O(1)\) で求めることができます。これは累積和の典型的な使い方です。

例えば、区間 \([L, R]\) でのペア数は、累積和配列 prefix_sum を使って以下のように求められます： $\( \text{count} = \text{prefix_sum}[R] - \text{prefix_sum}[L] \)$

このように前処理を行うことで、各クエリに高速に応答できます。

アルゴリズム

1. 各隣接ペアについて、色が同じかどうかを記録した配列 same を作成（サイズ \(N\)）
2. same の累積和配列 prefix_sum を構築（サイズ \(N+1\)）
3. 各クエリに対し、prefix_sum[R] - prefix_sum[L] を計算して結果を得る

計算量

• 時間計算量: \(O(N + Q)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 入力を高速に行うために sys.stdin.read を使用している
• 区間は1-indexedで入力されるので、内部処理では0-indexedに変換する必要がある
• same[N - 1] は使われないので0で埋めておく（明示的に初期化）
• 累積和の添字に注意（prefix_sum[i + 1] = prefix_sum[i] + same[i]）

## ソースコード

```python
import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    Q = int(data[1])
    C = list(map(int, data[2:2+N]))
    
    # 前処理：累積和配列を作成
    same = [0] * N
    for i in range(N - 1):
        if C[i] == C[i + 1]:
            same[i] = 1
        else:
            same[i] = 0
    same[N - 1] = 0  # 最後の要素は使わないが念のため

    
    # 累積和
    prefix_sum = [0] * (N + 1)
    for i in range(N):
        prefix_sum[i + 1] = prefix_sum[i] + same[i]
        
    # クエリ処理
    result = []
    index = 2 + N
    for _ in range(Q):
        L = int(data[index]) - 1  # 0-indexedにする
        R = int(data[index + 1]) - 1
        index += 2
        count = prefix_sum[R] - prefix_sum[L]
        result.append(str(count))
    
    print('\n'.join(result))

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。