概要

花壇の指定された区間内で、隣り合う区画の花の色が同じである箇所の数を、複数のクエリに対して高速に求める問題です。累積和を用いることで各クエリに \(O(1)\) で答えられます。

考察

素朴なアプローチとその問題点

各クエリ \((L_j, R_j)\) に対して、\(i = L_j\) から \(R_j - 1\) まで順に \(C_i = C_{i+1}\) かどうかを調べると、1つのクエリあたり最大 \(O(N)\) かかります。クエリが \(Q\) 個あるので、全体で \(O(NQ)\) となり、\(N, Q\) が最大 \(2 \times 10^5\) のとき \(4 \times 10^{10}\) 回の計算が必要になり、TLE（時間制限超過） になります。

重要な気づき

「区間内の条件を満たす個数を求める」という問題は、累積和（Prefix Sum） で高速化できる典型パターンです。

まず、隣り合う区画 \(i\) と \(i+1\) の色が同じかどうかを表す値を事前に計算しておきます。具体的には：

\[a_i = \begin{cases} 1 & (C_i = C_{i+1} \text{ のとき}) \\ 0 & (\text{それ以外}) \end{cases} \quad (1 \leq i \leq N-1)\]

クエリ \((L, R)\) の答えは \(a_L + a_{L+1} + \cdots + a_{R-1}\) です。これは \(a\) の累積和を前計算しておけば、引き算1回で求められます。

具体例

\(N = 5\), \(C = [3, 3, 5, 5, 5]\) の場合：

位置 \(i\)	1	2	3	4
\(C_i = C_{i+1}\)?	✓	✗	✓	✓
\(a_i\)	1	0	1	1

累積和 \(\text{prefix}\): \([0, 0, 1, 1, 2, 3]\)

クエリ \((L=2, R=5)\) の答え: \(\text{prefix}[5] - \text{prefix}[2] = 3 - 1 = 2\)（位置3と位置4で一致）

アルゴリズム

1. 前処理: 累積和配列 \(\text{prefix}\) を構築する。

   • \(\text{prefix}[0] = 0\), \(\text{prefix}[1] = 0\)
   • \(i = 2, 3, \ldots, N\) に対して：\(\text{prefix}[i] = \text{prefix}[i-1] + [C_{i-1} = C_i]\)
   • ここで \(\text{prefix}[i]\) は「位置 \(1\) から位置 \(i-1\) までの間で隣接同色となる箇所の累積個数」を意味します。

2. クエリ応答: 各クエリ \((L, R)\) に対して、答えは： $\(\text{prefix}[R] - \text{prefix}[L]\)\( これは区間 \)[L, R-1]\( における \)a_i$ の合計に対応します。

計算量

• 時間計算量: \(O(N + Q)\)（前処理に \(O(N)\)、各クエリに \(O(1)\)）
• 空間計算量: \(O(N)\)（累積和配列の分）

実装のポイント

• 1-indexed と 0-indexed の対応: 問題文は 1-indexed だが、Pythonのリストは 0-indexed なので、累積和配列を \(N+1\) の長さで作り、添字のずれに注意する。

• 累積和の引き算の式: \(\text{prefix}[R] - \text{prefix}[L]\) で区間 \([L, R-1]\) の合計が得られることを確認する。\(L\) ではなく \(L-1\) としてしまうミスに注意。

• 高速入出力: \(N, Q\) が大きいため、sys.stdin.readline や出力をまとめて sys.stdout.write で行うことで、Python でも TLE を回避できる。

  ソースコード

import sys
input = sys.stdin.readline

def main():
    N, Q = map(int, input().split())
    C = list(map(int, input().split()))
    
    # prefix[i] = number of positions j in [1, i-1] (1-indexed) where C[j] == C[j+1]
    # We define prefix[0] = 0, prefix[1] = 0
    # For i from 2 to N: prefix[i] = prefix[i-1] + (1 if C[i-1] == C[i-2] else 0)
    # Here C is 0-indexed, so C[i-1] and C[i-2] correspond to positions i and i-1 (1-indexed)
    
    prefix = [0] * (N + 1)
    for i in range(2, N + 1):
        prefix[i] = prefix[i - 1] + (1 if C[i - 1] == C[i - 2] else 0)
    
    # For query L, R: answer = prefix[R] - prefix[L]
    out = []
    for _ in range(Q):
        L, R = map(int, input().split())
        out.append(str(prefix[R] - prefix[L]))
    
    sys.stdout.write('\n'.join(out))

main()

---

この解説は claude4.6opus-thinking によって生成されました。