概要

各スタート地点 \(s\) について「累積重量が初めて \(K\) を超える倉庫番号」\(f(s)\) を求め、さらに区間 \([L,R]\) の \(\sum_{s=L}^{R} f(s)\) を高速に答える問題です。

考察

重要な気づき

スタート地点 \(s\) から東へ進むとき、条件は - \(A_s + A_{s+1} + \cdots + A_{t-1} \le K\) - しかし \(A_s + \cdots + A_t > K\) となる最初の \(t\) で止まる（それが \(f(s)\)）ということです。
つまり「\(K\) 以下で進める最大の到達位置」を \(r\) とすると、止まる位置は - \(r=N\) なら \(f(s)=N\)（最後まで超えない） - そうでなければ \(f(s)=r+1\)（次を取ったら超える倉庫） です。

素朴解が遅い理由

各 \(s\) ごとに \(s,s+1,s+2,\ldots\) と足していくと、最悪で - \(s=1\) で \(N\) 回 - \(s=2\) でも \(N-1\) 回 … となり、合計で \(O(N^2)\) になってしまい、\(N=2\times 10^5\) では間に合いません。

どう解決するか

\(A_i \ge 1\) なので、スタート地点 \(s\) を右に 1 進めると「許される区間の右端」も基本的に左には戻りません（単調に右へ進む）。
この性質を使って 尺取り法（two pointers） で全ての \(f(s)\) を \(O(N)\) で求めます。

さらに、クエリは \(\sum f(s)\) の区間和なので、\(f\) の累積和（prefix sum）を作れば各クエリは \(O(1)\) で答えられます。

アルゴリズム

1. 尺取り法で全ての \(f(l)\) を求める

左端を \(l=1..N\) と動かし、右端 \(r\) と区間和 \(ssum=\sum_{i=l}^{r} A_i\) を管理します。

• 初期状態: \(r=0\), \(ssum=0\)（空区間）
• 各 \(l\) について以下を行う：
  1. 可能な限り右端を伸ばす
     while r < N and ssum + A[r+1] <= K:
     として、\(K\) 以下で持てる限り \(r\) を右へ進め、\(ssum\) を更新する。
  2. 止まる倉庫番号を決める
     
     • もし \(r==N\) なら最後まで超えないので \(f(l)=N\)
     • そうでなければ、次の倉庫 \(r+1\) を取ると超えるので \(f(l)=r+1\) （なお、\(A_l > K\) の場合は \(r=l-1\) のままで、\(f(l)=l\) となる）
  3. 次の左端へ進める準備
     もし \(r \ge l\)（区間が空でない）なら、\(ssum\) から \(A_l\) を引いて左端を 1 つ進める。

こうすると \(r\) は全体で高々 \(N\) 回しか増えないため、全体で \(O(N)\) になります。

具体例（イメージ）

例えば \(A=[2,3,4,1], K=5\) のとき： - \(l=1\): \(2+3=5\) まで持てるので \(r=2\)、次 \(4\) で超える → \(f(1)=3\) - \(l=2\): 左を進めて和は \(3\)、\(3+4=7\) は不可 → \(r=2\)、次で超える → \(f(2)=3\) - \(l=3\): 和 \(0\) から \(4+1=5\) まで持てる → \(r=4=N\) → \(f(3)=4\) - \(l=4\): \(1\) だけ持てる → \(r=4=N\) → \(f(4)=4\)

2. \(f\) の累積和でクエリに答える

\(pref[i] = f(1)+f(2)+\cdots+f(i)\) を作ると、 [ \sum_{s=L}^{R} f(s) = pref[R] - pref[L-1] ] で各クエリを \(O(1)\) で処理できます。

計算量

• 時間計算量:
  
  • \(f\) の計算（尺取り法）: \(O(N)\)
    
  • 累積和: \(O(N)\)
    
  • クエリ処理: \(O(Q)\)
    合計で \(O(N+Q)\)
• 空間計算量: \(O(N)\)（配列 \(A,f,pref\)）

実装のポイント

• \(A_i\) や \(K\) が大きい（最大 \(10^{15}\) 付近）ので、和は 64bit 整数で扱う必要があります（Python なら自動でOK）。

• \(A_l > K\) のように「その倉庫の荷物を拾った瞬間に超える」ケースでは、\(r=l-1\) のままになり、\(f(l)=r+1=l\) となる点が自然に処理できるようにしています。

• 入力が大きいので、sys.stdin.buffer.read() を使った高速入力（FastScanner）で実行時間を安定させています。

  ソースコード

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

---

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