Official

C - 谷の数え上げ / Counting Valleys Editorial by admin Editorial for printing

DeepSeek V3

Overview

This problem requires efficiently counting the number of “valleys” within a specified interval (excluding both endpoints) for each query, given a sequence of elevations at checkpoints.

Analysis

The condition for a valley is that \(H_{i-1} > H_i < H_{i+1}\) holds. If we examine each point within the interval for every query, the worst-case time complexity becomes \(O(NQ)\), which cannot be processed in time under the constraints \(N, Q \leq 2 \times 10^5\). Therefore, we need to consider a method that performs preprocessing so that each query can be answered efficiently.

The key observation is that by recording valley positions in advance and using prefix sums, we can compute the number of valleys in any interval in \(O(1)\). This allows us to keep the overall time complexity to \(O(N + Q)\).

Algorithm

  1. Preprocessing:

    • For each position \(i\) (\(2 \leq i \leq N-1\)), determine whether it is a valley. Create an array is_valley that records \(1\) if it is a valley and \(0\) otherwise.
    • Build a prefix sum array prefix from the is_valley array. prefix[i] represents the total number of valleys from position \(1\) to \(i\).
  2. Query Processing:

    • For each query \([L, R]\), the number of valleys within the interval is computed as prefix[R-1] - prefix[L].
    • However, if the length of the interval is \(2\) or less, no valleys can exist, so we return \(0\).

Complexity

  • Time complexity: \(O(N + Q)\)
    • Preprocessing takes \(O(N)\), and each query is processed in \(O(1)\).
  • Space complexity: \(O(N)\)
    • For storing the arrays H, is_valley, and prefix.

Implementation Notes

  • Pay attention to array indexing: the input \(H\) is 0-indexed, but the checkpoint numbers in the problem are 1-indexed. In the implementation, the indices of is_valley are aligned to be 1-indexed.

  • When computing the prefix sum, to find the sum within the interval \([L, R]\), we use prefix[R-1] - prefix[L]. This is because both endpoints \(L\) and \(R\) are excluded from the valley determination.

    Source Code

import sys

def main():
    data = sys.stdin.read().split()
    it = iter(data)
    n = int(next(it))
    q = int(next(it))
    H = [int(next(it)) for _ in range(n)]
    
    is_valley = [0] * (n + 2)
    for i in range(1, n - 1):
        if H[i - 1] > H[i] < H[i + 1]:
            is_valley[i + 1] = 1
    
    prefix = [0] * (n + 2)
    for i in range(1, n + 1):
        prefix[i] = prefix[i - 1] + is_valley[i]
    
    out_lines = []
    for _ in range(q):
        L = int(next(it))
        R = int(next(it))
        if R - L < 2:
            out_lines.append("0")
        else:
            res = prefix[R - 1] - prefix[L]
            out_lines.append(str(res))
    
    print("\n".join(out_lines))

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.

posted:
last update: