C - 谷の数え上げ / Counting Valleys Editorial by admin Editorial for printing
GPT 5.2 HighOverview
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
- Prepare an array
is_valley, and for \(2 \le i \le N-1\), setis_valley[i]=1if the following holds:- \(H_{i-1} > H_i\) and \(H_i < H_{i+1}\)
- Build a prefix sum array
prefwherepref[i] = is_valley[1] + is_valley[2] + \cdots + is_valley[i]. - 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, andpref
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 notpref[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.
posted:
last update: