概要

一列に並んだ \(N\) 個の花の色が与えられたとき、指定された範囲 \([L, R]\) 内で「隣り合う花の色が同じである箇所」がいくつあるかを高速に求める問題です。

考察

1. 素直な方法（全探索）

各質問 \([L, R]\) に対して、左端の \(L\) から右端の \(R-1\) まで順番に隣り合う色をチェックしていく方法が考えられます。 しかし、この方法では 1 つの質問に最大で \(N-1\) 回の計算が必要です。質問の数は \(Q\) 個あるため、全体の計算量は \(O(N \times Q)\) となります。 本問題の制約は \(N, Q \leq 2 \times 10^5\) であるため、最大で \(4 \times 10^{10}\) 回程度の計算が必要になり、実行時間制限に間に合いません。

2. 累積和の活用

「特定の範囲内の合計を高速に求める」という問題は、累積和という手法を用いることで効率化できます。 まず、隣り合う区画の状態を数値化してみましょう。 - \(i\) 番目と \(i+1\) 番目の色が同じなら \(1\) - 違うなら \(0\)

という値を考えます。例えば花の色が 1 2 2 3 3 3 であれば、隣接する色の判定結果は 0, 1, 0, 1, 1 となります。 範囲 \([L, R]\) における「隣り合う同じ色の数」は、この \(0\) と \(1\) の数列における \(L\) 番目から \(R-1\) 番目までの合計値に相当します。

あらかじめ数列の先頭からの合計（累積和）を計算しておくことで、どんな範囲の合計も「引き算 1 回」で求められるようになります。

アルゴリズム

1. 判定配列の作成と累積和の計算: 長さ \(N+1\) の配列 \(P\) を用意します。\(P[i]\) には「1番目から \(i\) 番目までの区画の間にある『同じ色の隣接箇所』の総数」を格納します。

   • \(C_i = C_{i+1}\) のとき： \(P[i+1] = P[i] + 1\)
   • \(C_i \neq C_{i+1}\) のとき： \(P[i+1] = P[i]\) これを \(i=1\) から \(N-1\) まで順に計算します。

2. クエリへの回答: 範囲 \([L, R]\) が与えられたとき、求める答えは \(P[R] - P[L]\) となります。

   • \(P[R]\) は \(1\) から \(R\) までの隣接一致数
   • \(P[L]\) は \(1\) から \(L\) までの隣接一致数 この差を取ることで、\(L\) 番目より後の区画から \(R\) 番目までの区画に含まれる隣接一致箇所のみを抽出できます。

計算量

• 時間計算量: \(O(N + Q)\)
  • 累積和の構築に \(O(N)\)、各質問への回答に \(O(1)\) かかります。質問は \(Q\) 個あるため、全体で \(O(N + Q)\) となり、十分に高速です。
• 空間計算量: \(O(N)\)
  • 累積和を保持する配列 \(P\) のために \(O(N)\) のメモリを使用します。

実装のポイント

• 大量の入力処理: Pythonでは input() を繰り返すと時間がかかることがあります。sys.stdin.read().split() を使って一括で入力を読み込むことで、実行時間を大幅に短縮できます。

• インデックスの管理: 問題文は 1-indexed（1始まり）ですが、プログラミング言語の多くは 0-indexed（0始まり）です。累積和の配列を \(N+1\) のサイズで確保し、1-indexed のまま扱えるようにすると混乱が少なくなります。

• 出力の高速化: 各質問ごとに print するのではなく、結果をリストに貯めて最後に "\n".join() で一括出力することで、出力のオーバーヘッドを減らすことができます。

  ソースコード

import sys

def solve():
    # 入力をすべて読み込み、空白文字で分割してリストにする
    # 大量の入力を処理する場合、sys.stdin.read().split() が高速
    data = sys.stdin.read().split()
    if not data:
        return
    
    # N: 区画の数, Q: 質問の数
    N = int(data[0])
    Q = int(data[1])
    
    # 隣り合う区画の花の色が同じである箇所の累積和を計算する
    # P[i] は 1 番目から i 番目の区画までの間にある「同じ色の隣接箇所」の総数
    # 具体的には、P[i] = (C_1==C_2) + (C_2==C_3) + ... + (C_{i-1}==C_i)
    P = [0] * (N + 1)
    # 各区画の色 C_1, ..., C_N は data[2] から data[N+1] に格納されている
    for i in range(1, N):
        # i番目とi+1番目の花の色を比較 (0-indexedのdataでは 1+i と 2+i)
        if data[1 + i] == data[2 + i]:
            P[i + 1] = P[i] + 1
        else:
            P[i + 1] = P[i]
            
    # 質問は data[2 + N] 以降に L_j, R_j のペアで格納されている
    query_start = 2 + N
    results = []
    for j in range(Q):
        # 1-indexed の範囲 L から R が与えられる
        L = int(data[query_start + 2 * j])
        R = int(data[query_start + 2 * j + 1])
        
        # 範囲 [L, R] 内の隣接一致箇所の数は、累積和の差で求められる
        # P[R] は 1からRまでの隣接一致数、P[L] は 1からLまでの隣接一致数
        # 求めるのは LからRまでの隣接一致数なので P[R] - P[L]
        results.append(str(P[R] - P[L]))
        
    # 全ての質問の答えを改行区切りで一気に出力
    sys.stdout.write("\n".join(results) + "\n")

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-thinking によって生成されました。