Official

C - 谷の数え上げ / Counting Valleys Editorial by admin Editorial for printing

GPT 5.2 High

概要

各地点が「谷」かどうかを前計算し、その個数の累積和を使って、各クエリ区間内(両端除く)の谷の数を高速に答える問題です。

考察

谷の定義は「中央が両隣より真に低い」なので、地点 \(i\) が谷かどうかは \(H_{i-1}, H_i, H_{i+1}\) の3つだけで決まります。つまり、各 \(i\) について一度判定してしまえば、その後は「ある区間に谷が何個あるか」を数える問題になります。

素朴に各クエリごとに \(i=L_j+1\) から \(R_j-1\) まで走査して谷判定をすると、最悪で - 1クエリあたり \(O(N)\) - クエリが \(Q\) 個で合計 \(O(NQ)\) となり、\(N,Q \le 2\times 10^5\) では間に合いません。

そこで、 1. まず全地点について「谷なら1、違うなら0」の配列を作る 2. その累積和(prefix sum)を作る ことで、任意区間内の谷の数を差分1回で求められるようにします。

また問題文の注意通り、クエリ区間 \([L,R]\) では端点 \(L, R\) は判定対象外です。したがって数えるべきは \(L < i < R\) の谷、つまり添字範囲で言えば \(i \in [L+1, R-1]\) です。

アルゴリズム

  1. 配列 is_valley を用意し、\(2 \le i \le N-1\) について以下を満たすなら is_valley[i]=1 とする。
    • \(H_{i-1} > H_i\) かつ \(H_i < H_{i+1}\)
  2. pref[i] = is_valley[1] + is_valley[2] + \cdots + is_valley[i] となる累積和配列 pref を作る。
  3. 各クエリ \([L,R]\) について、数える範囲は \(i \in [L+1, R-1]\)。
    累積和を使うと個数は
    $\( \sum_{i=L+1}^{R-1} is\_valley[i] = pref[R-1] - pref[L] \)\( で求まる(`pref[x]` は \)1..x\( の和なので、\)1..L\( を引けば \)L+1..R-1$ が残る)。

具体例

例えば is_valley = [0, 0, 1, 0, 1, 0](1-indexedで、2と4が谷)だとして、クエリが \([L,R]=[1,5]\) のとき、 - 対象は \(i=2,3,4\)(両端除く) - 谷は \(i=2,4\) の2個
累積和なら pref[4] - pref[1] で一発です。

計算量

  • 時間計算量: 前計算 \(O(N)\)、各クエリ \(O(1)\) なので合計 \(O(N+Q)\)
  • 空間計算量: H, is_valley, pref により \(O(N)\)

実装のポイント

  • 谷判定は両隣が必要なので、\(i=2\) から \(N-1\) までのみ調べる(端は判定不能)。

  • クエリの答えは「端点除外」なので pref[R-1] - pref[L] になる点に注意(pref[R] - pref[L-1] ではない)。

  • 入力が大きいので、sys.stdin.buffer.read() でまとめて読み取ると高速です。

    ソースコード

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()

この解説は gpt-5.2-high によって生成されました。

posted:
last update: