概要

お店の商品価格の配列が与えられ、複数の区間クエリに対して各区間の合計値が予算上限 \(T\) を超えるかどうかを判定する問題です。

考察

この問題では、最大20万件のクエリに対して、各区間 \([L_j, R_j]\) の合計値を高速に計算する必要があります。素朴なアプローチとして、各クエリごとに直接配列を走査して合計値を計算すると、1クエリあたり \(O(N)\) の時間がかかり、全体で \(O(NQ)\) つまり最大 \(4 \times 10^{10}\) 回の計算が必要になり、制限時間内に処理できません。

この問題を効率的に解決するためには、事前に累積和を計算しておくことで、各クエリを定数時間 \(O(1)\) で処理できるようにするのが鍵となります。

アルゴリズム

累積和（Prefix Sum）と呼ばれる手法を使用します。具体的には以下の手順です：

1. 累積和配列の構築：

   • 長さ \(N+1\) の配列 prefix_sum を作成します
   • prefix_sum[0] = 0 と初期化します
   • \(i = 1\) から \(N\) まで、prefix_sum[i] = prefix_sum[i-1] + A[i-1] を計算します
   • これにより、prefix_sum[i] は先頭から \(i\) 番目までの要素の合計値を表します

2. クエリ処理：

   • 区間 \([L, R]\) の合計値は、prefix_sum[R] - prefix_sum[L-1] で計算できます
   • この合計値が \(T\) より大きいかどうかを判定します

例えば、\(A = [3, 1, 4, 1, 5]\)、\(L=2\)、\(R=4\) の場合： - prefix_sum[4] = 3+1+4+1 = 9 - prefix_sum[1] = 3 - 合計値 = \(9 - 3 = 7\) (\(A_2 + A_3 + A_4 = 1+4+1\))

計算量

• 時間計算量: \(O(N + Q)\)
  • 累積和配列の構築に \(O(N)\)
  • 各クエリの処理に \(O(1)\)、\(Q\) 回で \(O(Q)\)
• 空間計算量: \(O(N)\)
  • 累積和配列を格納するための \(O(N)\) のメモリ

実装のポイント

• 累積和配列のサイズは元の配列より1大きい \((N+1)\) にします

• インデックスに注意：元の配列の \(i\) 番目の要素は A[i-1] に対応します

• クエリの区間 \([L, R]\) の合計値は prefix_sum[R] - prefix_sum[L-1] で計算できます

• 大きな数値（\(T\) は最大 \(10^{14}\)）を扱うため、整数型のオーバーフローに注意します（Pythonでは自動で多倍長整数が使われるため問題ありません）

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    n = int(data[0])
    q = int(data[1])
    T = int(data[2])
    A = list(map(int, data[3:3+n]))
    queries = []
    index = 3 + n
    for i in range(q):
        L = int(data[index])
        R = int(data[index+1])
        queries.append((L, R))
        index += 2
        
    prefix_sum = [0] * (n + 1)
    for i in range(1, n + 1):
        prefix_sum[i] = prefix_sum[i-1] + A[i-1]
        
    results = []
    for (L, R) in queries:
        total = prefix_sum[R] - prefix_sum[L-1]
        if total > T:
            results.append("Yes")
        else:
            results.append("No")
            
    for res in results:
        print(res)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。