Overview

Given the colors of \(N\) flowers arranged in a row, the problem asks us to quickly determine how many positions within a specified range \([L, R]\) have “adjacent flowers of the same color.”

Analysis

1. Naive Approach (Brute Force)

For each query \([L, R]\), one could check adjacent colors sequentially from the left end \(L\) to \(R-1\). However, this method requires up to \(N-1\) computations per query. Since there are \(Q\) queries, the total time complexity is \(O(N \times Q)\). Given the constraints \(N, Q \leq 2 \times 10^5\), this would require up to about \(4 \times 10^{10}\) operations, which will not fit within the time limit.

2. Using Prefix Sums

The problem of “quickly computing a sum over a specific range” can be solved efficiently using the prefix sum technique. First, let’s convert the state of adjacent sections into numerical values: - \(1\) if the \(i\)-th and \((i+1)\)-th flowers have the same color - \(0\) otherwise

For example, if the flower colors are 1 2 2 3 3 3, the adjacency comparison results would be 0, 1, 0, 1, 1. The “number of adjacent same-colored pairs” in the range \([L, R]\) corresponds to the sum of this sequence of \(0\)s and \(1\)s from the \(L\)-th to the \((R-1)\)-th position.

By precomputing the running total (prefix sum) from the beginning of the sequence, any range sum can be obtained with “a single subtraction.”

Algorithm

1. Creating the indicator array and computing the prefix sum: Prepare an array \(P\) of length \(N+1\). \(P[i]\) stores “the total number of ‘adjacent same-color positions’ among the first \(i\) sections.”

   • If \(C_i = C_{i+1}\): \(P[i+1] = P[i] + 1\)
   • If \(C_i \neq C_{i+1}\): \(P[i+1] = P[i]\) This is computed sequentially for \(i=1\) through \(N-1\).

2. Answering queries: Given a range \([L, R]\), the answer is \(P[R] - P[L]\).

   • \(P[R]\) is the number of adjacent matches from position \(1\) to \(R\)
   • \(P[L]\) is the number of adjacent matches from position \(1\) to \(L\) By taking this difference, we can extract only the adjacent matching positions from after the \(L\)-th section up to the \(R\)-th section.

Complexity

• Time complexity: \(O(N + Q)\)
  • Building the prefix sum takes \(O(N)\), and answering each query takes \(O(1)\). Since there are \(Q\) queries, the total is \(O(N + Q)\), which is sufficiently fast.
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used for the prefix sum array \(P\).

Implementation Notes

• Handling large input: In Python, repeatedly calling input() can be slow. By reading all input at once using sys.stdin.read().split(), execution time can be significantly reduced.

• Index management: The problem statement uses 1-indexed (starting from 1), but most programming languages use 0-indexed (starting from 0). Allocating the prefix sum array with size \(N+1\) and handling it in 1-indexed fashion reduces confusion.

• Output optimization: Instead of calling print for each query, collecting results in a list and outputting them all at once with "\n".join() reduces output overhead.

  Source Code

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()

This editorial was generated by gemini-3-flash-thinking.