Overview

Given the colors of each section of flower beds arranged in a row, answer queries that ask for the number of pairs of adjacent sections with the same color within a specified interval.

Analysis

In this problem, for each interval, we need to determine “whether adjacent sections have the same color” and count the number of such pairs.

A naive approach would be to check each adjacent pair within the range \([L_j, R_j]\) for every query. However, this method takes \(O(N)\) per query in the worst case, resulting in \(O(Q \cdot N)\) overall. Since the constraints are \(N, Q \leq 2 \times 10^5\), this cannot be processed within the time limit (TLE).

Instead, we precompute “whether adjacent sections have the same color” at each position. Specifically, we prepare an array same of length \(N\), where same[i] = 1 when \(C[i] = C[i+1]\), and 0 otherwise.

Furthermore, by computing the prefix sum of this same array, we can determine the number of same-color pairs in any interval \([L, R)\) in \(O(1)\). This is a typical application of prefix sums.

For example, the number of pairs in the interval \([L, R]\) can be computed using the prefix sum array prefix_sum as follows: $\( \text{count} = \text{prefix_sum}[R] - \text{prefix_sum}[L] \)$

By performing this preprocessing, we can answer each query efficiently.

Algorithm

1. Create an array same (of size \(N\)) that records whether each adjacent pair has the same color
2. Build the prefix sum array prefix_sum of same (of size \(N+1\))
3. For each query, compute prefix_sum[R] - prefix_sum[L] to obtain the result

Complexity

• Time complexity: \(O(N + Q)\)
• Space complexity: \(O(N)\)

Implementation Notes

• sys.stdin.read is used for fast input

• Since intervals are given in 1-indexed format, they need to be converted to 0-indexed for internal processing

• same[N - 1] is not used, so it is filled with 0 (explicitly initialized)

• Pay attention to the indices of the prefix sum (prefix_sum[i + 1] = prefix_sum[i] + same[i])

  Source Code

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

This editorial was generated by qwen3-coder-480b.