C - 谷の数え上げ / Counting Valleys Editorial by admin Editorial for printing
DeepSeek V3Overview
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
Preprocessing:
- For each position \(i\) (\(2 \leq i \leq N-1\)), determine whether it is a valley. Create an array
is_valleythat records \(1\) if it is a valley and \(0\) otherwise. - Build a prefix sum array
prefixfrom theis_valleyarray.prefix[i]represents the total number of valleys from position \(1\) to \(i\).
- For each position \(i\) (\(2 \leq i \leq N-1\)), determine whether it is a valley. Create an array
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\).
- For each query \([L, R]\), the number of valleys within the interval is computed as
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, andprefix.
- For storing the arrays
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_valleyare 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: