Overview

Given a sequence of length \(N\), find the number of contiguous subsequences (intervals) whose sum of elements is at most \(K\).

Analysis

In this problem, if we brute-force all contiguous intervals and compute their sums, the time complexity becomes \(O(N^2)\), which is too slow for the constraint \(N \leq 2 \times 10^5\). Therefore, we need to efficiently count the number of intervals satisfying the condition.

A key observation is that “interval sums” can be computed quickly using prefix sums. Specifically, define the prefix sum array \(prefix\) of the sequence \(A\) as:

\[ prefix[i] = A_1 + A_2 + \cdots + A_i \]

Then the sum of the interval \([l, r]\) is:

\[ A_l + A_{l+1} + \cdots + A_r = prefix[r] - prefix[l-1] \]

This problem is essentially asking for “the number of pairs \((l, r)\) such that \(prefix[r] - prefix[l-1] \leq K\).” Rearranging this gives:

\[ prefix[l-1] \geq prefix[r] - K \]

In other words, for each right endpoint \(r\), we need to count how many values among \(prefix[0], prefix[1], \ldots, prefix[r-1]\) are at least \(prefix[r] - K\).

At this point, the prefix sum array is not necessarily non-decreasing, and since the search range is limited to the left side, we cannot maintain a sorted state within the search range at all times. However, since we are scanning along the index order of the prefix sums, binary search becomes effective. By using bisect_left, we can efficiently find the minimum index satisfying the condition.

Algorithm

1. Read the sequence \(A\) from input and construct the prefix sum array prefix.
2. For each right endpoint \(r = 1, 2, \ldots, N\), do the following:
   • Compute \(target = prefix[r] - K\).
   • Use binary search to find the minimum index \(pos\) in the array prefix[0..r-1] whose value is at least \(target\).
   • The number of valid \(l\) values, where \(l-1\) ranges over \(pos, pos+1, \ldots, r-1\), is \(r - pos\) in total.
   • Add this count to the answer.
3. Output the final answer.

Complexity

• Time complexity: \(O(N \log N)\)
  (because binary search is performed for each \(r\))
• Space complexity: \(O(N)\)
  (for storing the prefix sum array)

Implementation Notes

• Set the size of the prefix sum array to \(N+1\) with prefix[0] = 0, so that even when the left endpoint of the interval starts from 1, it can be handled naturally.

• When using Python’s bisect_left, the search range must be limited from 0 to r (i.e., prefix[:r]). This ensures that binary search is performed over the correct range.

  Source Code

import sys
from bisect import bisect_left

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    K = int(data[1])
    A = list(map(int, data[2:]))

    # 累積和を計算
    prefix = [0] * (N + 1)
    for i in range(N):
        prefix[i + 1] = prefix[i] + A[i]
    
    count = 0
    # 各右端 r に対して、条件を満たす左端 l の個数を数える
    for r in range(1, N + 1):
        # 区間 [l, r] の和 = prefix[r] - prefix[l-1] <= K
        # つまり prefix[l-1] >= prefix[r] - K
        target = prefix[r] - K
        # prefix[0..r-1] の中で、prefix[l-1] >= target となる最小の l-1 を見つける
        # これは prefix[0..r-1] が非減少なので二分探索可能
        pos = bisect_left(prefix, target, 0, r)  # prefix[0..r-1] の範囲で探索
        count += r - pos  # l-1 が pos, pos+1, ..., r-1 に対応する l が存在

    print(count)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.