概要

各クエリで指定された区間 \([L, R]\) の合計金額が予算上限 \(T\) を超えるかを判定します。多数の区間和を高速に求めるために累積和を使います。

考察

各買い出しで必要なのは区間和 \(A_L + A_{L+1} + \cdots + A_R\) です。
素朴に毎回 \(L\) から \(R\) まで足し合わせると、1回のクエリが最悪 \(O(N)\) かかり、全体で \(O(NQ)\) になります。制約では \(N, Q \le 2 \times 10^5\) なので、最悪だと約 \(4 \times 10^{10}\) 回の加算になり、時間内に終わりません（TLE）。

ここで重要な気づきは、区間和は累積和で一発計算できるということです。
累積和 \(pref[i] = A_1 + A_2 + \cdots + A_i\) を用意すると、

• 区間 \([L, R]\) の和は
  \(pref[R] - pref[L-1]\)

で求められます。これなら各クエリは \(O(1)\) です。

例：\(A = [3, 1, 4, 1, 5]\) のとき
\(pref = [0, 3, 4, 8, 9, 14]\)（先頭に \(pref[0]=0\) を置く）
区間 \([2,4]\) の和は \(pref[4]-pref[1]=9-3=6\) となります。

アルゴリズム

1. 長さ \(N+1\) の配列 \(pref\) を用意し、\(pref[0]=0\) とする。
2. \(i=1\) から \(N\) まで順に、\(pref[i] = pref[i-1] + A_i\) を計算する（累積和）。
3. 各クエリ \((L, R)\) について
   • \(total = pref[R] - pref[L-1]\) を求める
   • \(total > T\) なら Yes、そうでなければ No を出力する

計算量

• 時間計算量: 前処理が \(O(N)\)、各クエリが \(O(1)\) なので合計 \(O(N+Q)\)
• 空間計算量: 累積和配列に \(O(N)\)

実装のポイント

• 累積和は \(pref[0]=0\) を置くと、\(L=1\) のときも同じ式 \(pref[R]-pref[L-1]\) で扱えて楽です。

• 合計金額や \(T\) は最大で \(10^{14}\) 規模になり得るため、言語によっては 64bit 整数が必要です（Python は整数が大きくても扱えます）。

• 出力はクエリ数が多いので、文字列を配列に溜めて最後にまとめて出すと高速です。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, Q, T = map(int, input().split())
    A = list(map(int, input().split()))
    pref = [0] * (N + 1)
    s = 0
    for i, x in enumerate(A, 1):
        s += x
        pref[i] = s

    out_lines = []
    for _ in range(Q):
        L, R = map(int, input().split())
        total = pref[R] - pref[L - 1]
        out_lines.append("Yes" if total > T else "No")
    sys.stdout.write("\n".join(out_lines))

if __name__ == "__main__":
    main()

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