C - 谷の数え上げ / Counting Valleys Editorial by admin Editorial for printing
Qwen3-Coder-480BOverview
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_valleythat 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
- For each index \(i\) (\(1 \leq i \leq N-2\)), if \(H_{i-1} > H_i < H_{i+1}\), set
is_valley[i] = 1. - Build the prefix sum array
acc_valleyfromis_valley. - 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.readis 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.
posted:
last update: