公式

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

gemini-3-flash-thinking

Overview

Given elevation data for \(N\) points, the problem asks us to efficiently answer multiple queries (intervals \([L, R]\)) by counting the number of points that have lower elevation than both their neighbors (valleys).

Discussion

1. Valley Determination Condition

Whether a point \(i\) is a “valley” depends solely on the relationship between its elevation \(H_i\) and the elevations of its two neighbors \(H_{i-1}, H_{i+1}\). - Condition: \(H_{i-1} > H_i\) and \(H_i < H_{i+1}\)

This determination can be made independently for each point.

2. Naive Approach and Its Limitations

For each query \([L, R]\), if we check each point from \(L+1\) to \(R-1\) one by one to determine whether it is a valley, it takes \(O(N)\) time per query in the worst case. Since there are \(Q\) queries, the total computational complexity becomes \(O(N \times Q)\). In this problem, \(N, Q \leq 2 \times 10^5\), so up to approximately \(4 \times 10^{10}\) operations would be needed, which will not fit within the time limit (typically around 2 seconds).

3. Optimization Using Prefix Sums

Since the elevation data is not updated during the process, we can precompute “which points are valleys.” To efficiently find the “count” within a specific interval, the prefix sum technique is extremely effective.

  1. Prepare an array \(A\) of length \(N\), where \(A[i] = 1\) if point \(i\) is a valley, and \(A[i] = 0\) otherwise.
  2. Create a prefix sum array \(S\) from \(A\). \(S[k]\) represents the total number of valleys from the \(1\)st to the \(k\)th point.
  3. The number of valleys in the interval \((L, R)\), i.e., from the \((L+1)\)th to the \((R-1)\)th point, can be computed with just \(S[R-1] - S[L]\) in \(O(1)\) time.

Algorithm

  1. Flagging Valleys: For each point from \(i = 2\) to \(N-1\), check whether the valley condition is satisfied and record the result in an array (e.g., is_valley_count).
  2. Computing the Prefix Sum: Create a prefix sum array prefix_sum based on the above array. prefix_sum[i] = prefix_sum[i-1] + (1 if point i is a valley, 0 otherwise)
  3. Answering Queries: For each query \([L, R]\), the answer is prefix_sum[R-1] - prefix_sum[L]. ※ For short intervals where \(R-1 < L+1\), this calculation yields \(0\) or a negative value, but if computed according to the definition of prefix sums, it will correctly evaluate to \(0\).

Complexity

  • Time Complexity: \(O(N + Q)\)
    • Valley determination and prefix sum construction take \(O(N)\), and answering each query takes \(O(1)\), so the overall complexity is \(O(N + Q)\).
  • Space Complexity: \(O(N)\)
    • \(O(N)\) memory is used to store the elevation data and the prefix sum array.

Implementation Notes

  • Fast Input/Output: In Python, repeatedly calling input() is slow, so it is more efficient to read all input at once using sys.stdin.read().split() or similar methods.

  • Index Management: The problem statement uses 1-indexed (starting from 1), but program arrays are often 0-indexed (starting from 0), so be careful about index offsets.

  • Boundary Conditions: Since the query range is \(L < i < R\), make sure not to make mistakes with the prefix sum range (subtract the prefix sum up to point \(L\), and use the prefix sum up to point \(R-1\)).

    Source Code

import sys

def solve():
    # Use fast I/O: read all input at once from standard input
    data = sys.stdin.read().split()
    if not data:
        return
    
    # Convert all input strings to integers at once for efficiency
    # This is faster in Python than converting them one by one in a loop
    nums = list(map(int, data))
    
    N = nums[0]
    Q = nums[1]
    
    # H[0]...H[N-1] correspond to checkpoint elevations H_1...H_N
    H = nums[2:2+N]
    
    # prefix_sum[i] will store the cumulative count of valleys from checkpoint 1 to i.
    # Checkpoints are 1-indexed (1 to N).
    # A checkpoint i (2 <= i <= N-1) is a valley if H[i-2] > H[i-1] < H[i].
    # We initialize an array of size N+1 to handle 1-based indexing easily.
    is_valley_count = [0] * (N + 1)
    for j in range(1, N - 1):
        # j is the 0-based index in H, so H[j] corresponds to checkpoint i = j+1.
        # Checkpoint i is a valley if the elevation at i-1 > elevation at i < elevation at i+1.
        if H[j-1] > H[j] < H[j+1]:
            is_valley_count[j+1] = 1
    
    # Compute the prefix sums from the is_valley_count array.
    # prefix_sum[i] = number of valleys in checkpoints {1, 2, ..., i}.
    prefix_sum = [0] * (N + 1)
    for i in range(1, N + 1):
        prefix_sum[i] = prefix_sum[i-1] + is_valley_count[i]
        
    # Process each of the Q queries.
    results = []
    # Query parameters L_j and R_j start from nums[2+N] onwards.
    query_start_idx = 2 + N
    for k in range(Q):
        L = nums[query_start_idx + 2 * k]
        R = nums[query_start_idx + 2 * k + 1]
        
        # The query asks for the number of valleys at checkpoints i such that L < i < R.
        # This range of checkpoints is {L+1, L+2, ..., R-1}.
        # The count of valleys in this range is prefix_sum[R-1] - prefix_sum[L].
        # Note: If R - 1 < L + 1 (i.e., R - L < 2), the range is empty.
        # Since L < R, R-1 >= L. If R-1 == L, the result is correctly 0.
        ans = prefix_sum[R-1] - prefix_sum[L]
        results.append(str(ans))
        
    # Output all results at once, separated by newlines, for performance.
    sys.stdout.write("\n".join(results) + "\n")

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-thinking.

投稿日時:
最終更新: