概要

全ての要素が正の配列 \(V\) に対し、連続区間の和が \(K\) 以上となる区間 \((l,r)\) の個数を数えます。

考察

区間和を愚直に全探索すると、各 \(l\) について \(r\) を伸ばして和を計算するため \(O(N^2)\) となり、\(N \le 2\times 10^5\) では間に合いません。

ここで重要な観察は \(V_i \ge 1\)（全て正） であることです。
この性質により、右端 \(r\) を右に動かすほど区間和 \(V_l+\cdots+V_r\) は 単調増加 します。したがって、

• 固定した左端 \(l\) に対して「和が \(K\) 以上になる最小の右端」を一度見つければ、
• それより右に伸ばした区間はすべて条件を満たす

ということが言えます。

例えば、ある \(l\) で最小の右端が \(r\)（\([l,r]\) が初めて \(K\) 以上）なら、\([l,r],[l,r+1],\dots,[l,N]\) は全部OKなので、個数は \(N-r+1\) です。

この「最小の右端」は、次の \(l+1\) に移るときに大きく左へ戻ることはなく（正の数なので必要な長さが急に短くなりにくい）、右端を1本のポインタとして前に進め続けることで全体を \(O(N)\) で処理できます。

アルゴリズム

しゃくとり法（Two Pointers / Sliding Window） を用います。

• 右端ポインタを r（半開区間で \([l,r)\) を表す）、
• 現在の区間和を s とします。

手順： 1. 初期状態 l=0, r=0, s=0。 2. 各 l について、s < K の間は r を右へ動かして s += V[r] を行う（ただし r < N の範囲）。 3. もし s >= K になったら、右端をこれ以上伸ばしても和は増えるだけなので、条件を満たす区間の数は
\(N - (r-1)\) 個
ただしコードでは r が「次に足す位置」（半開区間）なので、個数は N - r + 1 を加算する。 4. 次の l へ進むために、左端の要素を除いて s -= V[l]。

r は全体で高々 \(N\) 回しか増えないため、高速に動きます。

計算量

• 時間計算量: \(O(N)\)（l も r も最大で \(N\) 回ずつしか動かない）
• 空間計算量: \(O(1)\)（入力配列以外は定数）

実装のポイント

• 半開区間 \([l,r)\) で管理すると、r を進める処理と個数計算が整理しやすいです（コードの ans += N - r + 1 はこのため）。

• s >= K になった時点で、右端をそれ以上にした区間はすべて条件を満たすため、まとめて数えられます。

• K や区間和は最大で \(10^{14}\) 程度になり得ますが、Python の int は任意精度なので安全です。

  ソースコード

import sys

def main():
    it = map(int, sys.stdin.buffer.read().split())
    N = next(it)
    K = next(it)
    A = [next(it) for _ in range(N)]

    r = 0
    s = 0
    ans = 0

    for l in range(N):
        while r < N and s < K:
            s += A[r]
            r += 1
        if s >= K:
            ans += N - r + 1
        s -= A[l]

    print(ans)

if __name__ == "__main__":
    main()

---

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