この問題は尺取り法を用いることで解くことができます。尺取り法については以下の記事が詳しいのでそちらを参照してください。

• しゃくとり法 (尺取り法) の解説と、それを用いる問題のまとめ

この問題は以下のようなアルゴリズムで解くことができます：

• \(l=1,r=1,s=0\) とする。 \(s\) には \(A_l,A_{l+1},\ldots,A_{r-1}\) の総和を保持する変数である。
• 以下の一連の操作を \(N\) 回行う。
  • \(s \le K\) が満たされる間、 \(s\) に \(A_r\) を足し \(r\) に \(1\) を足す。
  • \(f(l)=r\) とする。
  • \(s\) から \(A_l\) を引き、\(l\) に \(1\) を足す。

各 \(f\) の値が求まったあとは、累積和を計算することで各クエリに対して \(O(1)\) 時間で答えを計算することができます。

以上を適切に実装することでこの問題に正答することができます。計算量は \(O(N+Q)\) 時間です。

実装例(Python3)

n, k, q = map(int, input().split())
a = list(map(int, input().split()))
ans = [0] * (n + 1)
r, s = 0, 0
for l in range(n):
    while r != n and s <= k:
        s += a[r]
        r += 1
    ans[l + 1] = ans[l] + r
    s -= a[l]
for _ in range(q):
    l, r = map(int, input().split())
    print(ans[r] - ans[l - 1])