Overview

This problem asks us to quickly answer, for each query interval \([L, R]\), the number of positions where adjacent sections have the same color. We create an array of adjacent matches and use its prefix sum to compute interval sums.

Analysis

What we want to find is the count of \(i\) (\(L \le i \le R-1\)) such that \(C_i = C_{i+1}\) within the interval.

A naive approach of checking from \(i=L\) to \(R-1\) for each query costs \(O(N)\) per query and \(O(NQ)\) overall. Given the constraints \(N,Q \le 2\times 10^5\), this results in approximately \(4\times 10^{10}\) comparisons in the worst case, which will definitely time out.

The key observation is as follows:

• Whether adjacent elements are the same is uniquely determined for each position \(i\) by looking at \(C_i\) and \(C_{i+1}\)
• Therefore, we can first create a flag \(A_i = [C_i = C_{i+1}]\) for each \(i\) (1 if true, 0 if false)
• The answer to each query is simply the interval sum \(A_L + A_{L+1} + \cdots + A_{R-1}\)

Interval sums can be answered in \(O(1)\) by precomputing a prefix sum.

Example: - When \(C = [1,1,2,2,2]\)
The adjacent match flags are \(A = [1,0,1,1]\) (matches for pairs (1,2),(2,3),(3,4),(4,5)) - For query \([L,R]=[2,5]\), we look at \(i=2..4\), so \(A_2+A_3+A_4 = 0+1+1=2\)

Algorithm

1. Read array \(C\).
2. Build a prefix sum pref of the adjacent match flags.
   • Define pref[i] as “the number of matches from the beginning up to position \(i\) (precisely, from adjacent pair \((1,2)\) to \((i,i+1)\))”.
   • In implementation, set pref[0]=0, and for \(i=1..N-1\):
     pref[i] = pref[i-1] + (C[i-1]==C[i])
3. For each query \([L,R]\), we need the number of matches for \(i=L..R-1\).
   • This can be computed using the prefix sum as pref[R-1] - pref[L-1].
   • (Since pref is 0-indexed and the input \(L,R\) are 1-indexed, this is the resulting formula)

Complexity

• Time complexity: Preprocessing \(O(N)\), each query \(O(1)\), so the total is \(O(N+Q)\)
• Space complexity: \(O(N)\) for the prefix sum array, etc.

Implementation Notes

• Be careful about index offsets (1-indexed vs 0-indexed). The input \(L,R\) are 1-indexed, but the Python array C is 0-indexed.

• The key point is defining pref so that pref[R-1] - pref[L-1] gives the “flag sum over \([L, R-1]\)”.

• Since \(N,Q\) can be large, using sys.stdin.buffer.read() for fast input helps ensure stable performance.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    Q = next(it)
    C = [next(it) for _ in range(N)]

    pref = [0] * N  # pref[i] = sum of equal-adjacent flags up to position i (1-based for flags)
    for i in range(1, N):
        pref[i] = pref[i - 1] + (1 if C[i - 1] == C[i] else 0)

    out_lines = []
    for _ in range(Q):
        L = next(it)
        R = next(it)
        # count flags in [L, R-1] => pref[R-1] - pref[L-1]
        out_lines.append(str(pref[R - 1] - pref[L - 1]))

    sys.stdout.write("\n".join(out_lines))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.