公式

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

GPT 5.2 High

Overview

This problem requires precomputing whether each point is a “valley,” then using a prefix sum of those counts to quickly answer the number of valleys within each query interval (excluding both endpoints).

Analysis

A valley is defined as “the center is strictly lower than both neighbors,” so whether point \(i\) is a valley depends only on three values: \(H_{i-1}, H_i, H_{i+1}\). This means once we determine the valley status for each \(i\), the problem reduces to counting how many valleys exist in a given interval.

A naive approach of scanning from \(i=L_j+1\) to \(R_j-1\) for each query to check valley status would result in: - \(O(N)\) per query in the worst case - \(O(NQ)\) total for \(Q\) queries which is too slow for \(N,Q \le 2\times 10^5\).

Instead, we: 1. First create an array where each element is 1 if the point is a valley, 0 otherwise 2. Build a prefix sum of that array

This allows us to compute the number of valleys in any interval with a single subtraction.

Also, as noted in the problem statement, for a query interval \([L,R]\), the endpoints \(L\) and \(R\) are excluded from consideration. Therefore, we need to count valleys for \(L < i < R\), i.e., indices in the range \(i \in [L+1, R-1]\).

Algorithm

  1. Prepare an array is_valley, and for \(2 \le i \le N-1\), set is_valley[i]=1 if the following holds:
    • \(H_{i-1} > H_i\) and \(H_i < H_{i+1}\)
  2. Build a prefix sum array pref where pref[i] = is_valley[1] + is_valley[2] + \cdots + is_valley[i].
  3. For each query \([L,R]\), the range to count is \(i \in [L+1, R-1]\). Using the prefix sum, the count is: $\( \sum_{i=L+1}^{R-1} is\_valley[i] = pref[R-1] - pref[L] \)\( (Since `pref[x]` is the sum from \)1..x\(, subtracting \)1..L\( leaves \)L+1..R-1$.)

Concrete Example

For example, suppose is_valley = [0, 0, 1, 0, 1, 0] (1-indexed, where positions 2 and 4 are valleys), and the query is \([L,R]=[1,5]\): - The target is \(i=2,3,4\) (excluding both endpoints) - The valleys are at \(i=2,4\), giving 2 Using the prefix sum, this is computed instantly as pref[4] - pref[1].

Complexity

  • Time complexity: \(O(N)\) for precomputation, \(O(1)\) per query, so \(O(N+Q)\) in total
  • Space complexity: \(O(N)\) for H, is_valley, and pref

Implementation Notes

  • Valley checking requires both neighbors, so only check from \(i=2\) to \(N-1\) (endpoints cannot be evaluated).

  • Since the answer for each query excludes the endpoints, the result is pref[R-1] - pref[L] — note that it is not pref[R] - pref[L-1].

  • Since the input can be large, reading all at once with sys.stdin.buffer.read() is faster.

    Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    Q = next(it)

    H = [0] * (N + 1)
    for i in range(1, N + 1):
        H[i] = next(it)

    is_valley = [0] * (N + 1)
    for i in range(2, N):
        if H[i - 1] > H[i] and H[i] < H[i + 1]:
            is_valley[i] = 1

    pref = [0] * (N + 1)
    for i in range(1, N + 1):
        pref[i] = pref[i - 1] + is_valley[i]

    out = []
    for _ in range(Q):
        L = next(it)
        R = next(it)
        out.append(str(pref[R - 1] - pref[L]))

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

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.

投稿日時:
最終更新: