Overview

This problem asks us to quickly answer multiple queries, each requesting the number of positions within a specified interval of a flower bed where adjacent sections have the same flower color. By using prefix sums, we can answer each query in \(O(1)\).

Analysis

Naive Approach and Its Issues

For each query \((L_j, R_j)\), if we check whether \(C_i = C_{i+1}\) for each \(i\) from \(L_j\) to \(R_j - 1\), a single query takes up to \(O(N)\) time. Since there are \(Q\) queries, the total complexity becomes \(O(NQ)\). When \(N, Q\) are at most \(2 \times 10^5\), this requires \(4 \times 10^{10}\) operations, resulting in TLE (Time Limit Exceeded).

Key Insight

The problem of “counting the number of elements satisfying a condition within an interval” is a classic pattern that can be optimized using Prefix Sums.

First, we precompute a value indicating whether adjacent sections \(i\) and \(i+1\) have the same color. Specifically:

\[a_i = \begin{cases} 1 & (C_i = C_{i+1}) \\ 0 & (\text{otherwise}) \end{cases} \quad (1 \leq i \leq N-1)\]

The answer to query \((L, R)\) is \(a_L + a_{L+1} + \cdots + a_{R-1}\). If we precompute the prefix sums of \(a\), this can be obtained with a single subtraction.

Concrete Example

For \(N = 5\), \(C = [3, 3, 5, 5, 5]\):

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

Prefix sum \(\text{prefix}\): \([0, 0, 1, 1, 2, 3]\)

Answer for query \((L=2, R=5)\): \(\text{prefix}[5] - \text{prefix}[2] = 3 - 1 = 2\) (matches at positions 3 and 4)

Algorithm

1. Preprocessing: Build the prefix sum array \(\text{prefix}\).

   • \(\text{prefix}[0] = 0\), \(\text{prefix}[1] = 0\)
   • For \(i = 2, 3, \ldots, N\): \(\text{prefix}[i] = \text{prefix}[i-1] + [C_{i-1} = C_i]\)
   • Here, \(\text{prefix}[i]\) represents “the cumulative count of adjacent same-color positions from position \(1\) to position \(i-1\).”

2. Query Response: For each query \((L, R)\), the answer is: $\(\text{prefix}[R] - \text{prefix}[L]\)\( This corresponds to the sum of \)a_i\( over the interval \)[L, R-1]$.

Complexity

• Time complexity: \(O(N + Q)\) (\(O(N)\) for preprocessing, \(O(1)\) per query)
• Space complexity: \(O(N)\) (for the prefix sum array)

Implementation Notes

• 1-indexed vs 0-indexed correspondence: The problem statement uses 1-indexed notation, but Python lists are 0-indexed. Create the prefix sum array with length \(N+1\) and be careful about index offsets.

• Prefix sum subtraction formula: Verify that \(\text{prefix}[R] - \text{prefix}[L]\) gives the sum over the interval \([L, R-1]\). Be careful not to mistakenly use \(L-1\) instead of \(L\).

• Fast I/O: Since \(N, Q\) can be large, use sys.stdin.readline for input and batch output with sys.stdout.write to avoid TLE in Python.

  Source Code

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

---

This editorial was generated by claude4.6opus-thinking.