Overview

For each starting position \(s\), we need to find \(f(s)\), the “warehouse number where the cumulative weight first exceeds \(K\)”, and then quickly answer queries of the form \(\sum_{s=L}^{R} f(s)\) over an interval \([L,R]\).

Analysis

Key Observation

When moving east from starting position \(s\), the conditions are: - \(A_s + A_{s+1} + \cdots + A_{t-1} \le K\) - But \(A_s + \cdots + A_t > K\)

You stop at the first such \(t\) (which is \(f(s)\)).
In other words, if we let \(r\) be the “maximum reachable position while staying at or below \(K\)”, then the stopping position is: - If \(r=N\), then \(f(s)=N\) (never exceeds the limit through the end) - Otherwise, \(f(s)=r+1\) (the warehouse where picking up the next item causes it to exceed)

Why the Naive Solution Is Too Slow

If for each \(s\) we sum \(A_s, A_{s+1}, A_{s+2}, \ldots\) one by one, in the worst case: - \(s=1\) takes \(N\) steps - \(s=2\) takes \(N-1\) steps …

The total becomes \(O(N^2)\), which is too slow for \(N=2\times 10^5\).

How to Solve It

Since \(A_i \ge 1\), when the starting position \(s\) moves one step to the right, the “right endpoint of the valid interval” essentially never moves back to the left (it moves monotonically to the right).
Using this property, we can compute all \(f(s)\) in \(O(N)\) with the two pointers technique.

Furthermore, since queries ask for interval sums \(\sum f(s)\), we can build a prefix sum array of \(f\) and answer each query in \(O(1)\).

Algorithm

1. Compute all \(f(l)\) using the two pointers technique

We move the left endpoint \(l=1..N\) and maintain the right endpoint \(r\) and the interval sum \(ssum=\sum_{i=l}^{r} A_i\).

• Initial state: \(r=0\), \(ssum=0\) (empty interval)
• For each \(l\), do the following:
  1. Extend the right endpoint as far as possible
     while r < N and ssum + A[r+1] <= K:
     Advance \(r\) to the right as long as the total stays at or below \(K\), updating \(ssum\).
  2. Determine the stopping warehouse number
     
     • If \(r==N\), the limit is never exceeded, so \(f(l)=N\)
     • Otherwise, picking up the next warehouse \(r+1\) would exceed the limit, so \(f(l)=r+1\)
       (Note: if \(A_l > K\), then \(r\) remains at \(l-1\), so \(f(l)=l\))
  3. Prepare to advance to the next left endpoint
     If \(r \ge l\) (the interval is non-empty), subtract \(A_l\) from \(ssum\) and advance the left endpoint by one.

Since \(r\) increases at most \(N\) times in total, the overall complexity is \(O(N)\).

Concrete Example (Illustration)

For example, with \(A=[2,3,4,1], K=5\): - \(l=1\): Can carry up to \(2+3=5\), so \(r=2\); next item \(4\) exceeds → \(f(1)=3\) - \(l=2\): After advancing left, sum is \(3\); \(3+4=7\) is not allowed → \(r=2\); next exceeds → \(f(2)=3\) - \(l=3\): From sum \(0\), can carry up to \(4+1=5\) → \(r=4=N\) → \(f(3)=4\) - \(l=4\): Can carry only \(1\) → \(r=4=N\) → \(f(4)=4\)

2. Answer queries using prefix sums of \(f\)

By building \(pref[i] = f(1)+f(2)+\cdots+f(i)\), we get: [ \sum_{s=L}^{R} f(s) = pref[R] - pref[L-1] ] which allows each query to be processed in \(O(1)\).

Complexity

• Time complexity:
  
  • Computing \(f\) (two pointers): \(O(N)\)
    
  • Prefix sums: \(O(N)\)
    
  • Query processing: \(O(Q)\)
    Total: \(O(N+Q)\)
• Space complexity: \(O(N)\) (arrays \(A, f, pref\))

Implementation Notes

• \(A_i\) and \(K\) can be large (up to around \(10^{15}\)), so sums must be handled with 64-bit integers (in Python this is automatic).

• In cases like \(A_l > K\), where “picking up that warehouse’s cargo immediately exceeds the limit”, \(r\) stays at \(l-1\), and \(f(l)=r+1=l\) is naturally handled.

• Since the input can be large, fast input using sys.stdin.buffer.read() (FastScanner) is used to keep execution time stable.

  Source Code

import sys


class FastScanner:
    __slots__ = ("data", "n", "i")

    def __init__(self):
        self.data = sys.stdin.buffer.read()
        self.n = len(self.data)
        self.i = 0

    def next_int(self):
        data = self.data
        n = self.n
        i = self.i
        while i < n and data[i] <= 32:
            i += 1
        num = 0
        while i < n and data[i] > 32:
            num = num * 10 + (data[i] - 48)
            i += 1
        self.i = i
        return num


def main():
    fs = FastScanner()
    N = fs.next_int()
    K = fs.next_int()
    Q = fs.next_int()

    A = [0] * (N + 1)
    for i in range(1, N + 1):
        A[i] = fs.next_int()

    f = [0] * (N + 1)
    r = 0
    ssum = 0

    for l in range(1, N + 1):
        if r < l - 1:
            r = l - 1
            ssum = 0

        while r < N and ssum + A[r + 1] <= K:
            r += 1
            ssum += A[r]

        if r == N:
            f[l] = N
        else:
            f[l] = r + 1  # may equal l when r == l-1

        if r >= l:
            ssum -= A[l]

    pref = [0] * (N + 1)
    for i in range(1, N + 1):
        pref[i] = pref[i - 1] + f[i]

    out = []
    for _ in range(Q):
        L = fs.next_int()
        R = fs.next_int()
        out.append(str(pref[R] - pref[L - 1]))
    sys.stdout.write("\n".join(out))


if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.