公式

C - 谷の数え上げ / Counting Valleys 解説 by admin 印刷ページ

Qwen3-Coder-480B

Overview

This is a query processing problem where, for each interval, we need to efficiently find the number of checkpoints that are “valleys” within the interval.

Analysis

In this problem, for each interval \([L_j, R_j]\), we need to count the number of “valleys” among the checkpoints excluding both endpoints.

A “valley” here means that a checkpoint \(i\) satisfies \(H_{i-1} > H_i < H_{i+1}\). In other words, the condition is that it is strictly lower than both of its neighbors.

A naive approach would be to check each index within the interval one by one for each query to determine whether it is a valley, but this results in a computational complexity of up to \(O(N \cdot Q)\), which is too slow (TLE) given the constraints \(N, Q \sim 2 \times 10^5\).

Therefore, we consider “preprocessing whether each index is a valley in advance, and enabling fast range sum queries.” Specifically:

  • For each index \(i\), create an array is_valley that records whether it is a valley as \(0/1\).
  • By computing the prefix sum of this array, we can determine the number of valleys within any interval \([L, R]\) in constant time.

By utilizing this prefix sum, the computation for answering each query becomes \(O(1)\), and the overall complexity becomes \(O(N + Q)\).

Also, since the problem states that “the endpoints are excluded from valley determination,” we only count within the range \([L+1, R-1]\). If \(L+1 > R-1\), then no valleys exist in that interval, so the answer is \(0\).

For example, given the following input:

H = [5, 2, 4, 1, 6]

The valleys are at index \(2\) (value=2) and index \(4\) (value=1) (1-indexed). Therefore, is_valley = [0, 1, 0, 1, 0], and by computing the prefix sum, we can quickly determine the number of valleys within any interval.

Algorithm

  1. For each index \(i\) (\(1 \leq i \leq N-2\)), if \(H_{i-1} > H_i < H_{i+1}\), set is_valley[i] = 1.
  2. Build the prefix sum array acc_valley from is_valley.
  3. For each query \([L_j, R_j]\), compute the number of valleys in the interval \([L_j+1, R_j-1]\) as acc_valley[R_j-1] - acc_valley[L_j].

Complexity

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

Implementation Notes

  • Using 1-indexed prefix sums simplifies boundary handling.

  • When the query interval is too narrow for any valley to exist (\(L+1 > R-1\)), the answer must be \(0\).

  • sys.stdin.read is used for fast input reading.

    Source Code

import sys
from itertools import accumulate

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    Q = int(data[1])
    H = list(map(int, data[2:N+2]))
    
    # 前処理:各位置が谷かどうかを判定し、累積和を計算
    is_valley = [0] * N
    for i in range(1, N-1):
        if H[i-1] > H[i] < H[i+1]:
            is_valley[i] = 1
    
    # 累積和配列を作成(1-indexed)
    acc_valley = [0] * (N + 1)
    for i in range(N):
        acc_valley[i+1] = acc_valley[i] + is_valley[i]
    
    # クエリ処理
    results = []
    idx = N + 2
    for _ in range(Q):
        L = int(data[idx])
        R = int(data[idx+1])
        idx += 2
        # 区間[L,R]内の谷の数を求める(両端は含まない)
        # 谷の判定対象は L+1 から R-1 まで
        if L + 1 > R - 1:
            results.append(0)
        else:
            count = acc_valley[R-1] - acc_valley[L]
            results.append(count)
    
    print('\n'.join(map(str, results)))

if __name__ == "__main__":
    main()

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

投稿日時:
最終更新: