概要

\(N\) 個の畑を \(M\) 個の連続した区画に分けたとき、各区画の収穫量合計（生産力）の最大値と最小値の差を求める問題です。

考察

問題を解くための重要な気づき

各区画の生産力は「連続する畑の収穫量の合計」です。例えば、畑 \(L\) から畑 \(R\) までの区画の生産力は \(A_L + A_{L+1} + \cdots + A_R\) となります。

素朴なアプローチの問題点

各区画について、その範囲の畑の収穫量を毎回足し合わせる方法を考えてみましょう。

区画ごとに: A[L] + A[L+1] + ... + A[R] を計算

この方法では、1つの区画の計算に最大 \(O(N)\) かかり、\(M\) 個の区画があるため、全体で \(O(NM)\) の時間がかかります。\(N, M\) が最大 \(2 \times 10^5\) の場合、最悪で約 \(4 \times 10^{10}\) 回の計算が必要となり、TLE（時間超過）になってしまいます。

解決策：累積和を使う

累積和（prefix sum） を使えば、連続する区間の合計を \(O(1)\) で求められます。

累積和配列 \(S\) を以下のように定義します： - \(S[0] = 0\) - \(S[i] = A_1 + A_2 + \cdots + A_i\)（\(i \geq 1\)）

すると、畑 \(L\) から畑 \(R\) までの合計は： $\(A_L + A_{L+1} + \cdots + A_R = S[R] - S[L-1]\)$

で計算できます。

具体例

畑の収穫量が \(A = [3, 1, 4, 1, 5]\) の場合：

\(i\)	0	1	2	3	4	5
\(S[i]\)	0	3	4	8	9	14

• 畑2から畑4の合計: \(S[4] - S[1] = 9 - 3 = 6\)（実際 \(1 + 4 + 1 = 6\) ✓）

アルゴリズム

1. 累積和の構築: 配列 \(A\) から累積和配列 \(S\) を作成する
2. 各区画の生産力計算: 各区画 \((L_j, R_j)\) に対して、生産力 \(S[R_j] - S[L_j - 1]\) を \(O(1)\) で計算
3. 最大値・最小値の更新: 計算した生産力を使って、最大値と最小値を更新
4. 差を出力: 最大値 \(-\) 最小値 を出力

計算量

• 時間計算量: \(O(N + M)\)

  • 累積和の構築に \(O(N)\)
  • 各区画の生産力計算に \(O(M)\)（各区画 \(O(1)\)）

• 空間計算量: \(O(N)\)

  • 累積和配列のサイズ

実装のポイント

1. 1-indexed と 0-indexed の変換:

   • 問題文では畑の番号が \(1\) から始まる（1-indexed）
   • Pythonの配列は \(0\) から始まる（0-indexed）
   • 累積和配列を prefix_sum[i+1] = prefix_sum[i] + A[i] として構築し、区間 \([L, R]\) の合計を prefix_sum[R] - prefix_sum[L-1] で求める

2. オーバーフローへの注意:

   • \(A_i\) は最大 \(10^9\)、畑は最大 \(2 \times 10^5\) 個なので、合計は最大約 \(2 \times 10^{14}\)
   • Pythonでは整数のオーバーフローは自動的に処理されるため問題なし（C++などでは long long が必要）

3. 高速な入力:

   • sys.stdin.readline を使うことで、大量の入力を高速に読み込める

     ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    
    # 累積和を計算
    prefix_sum = [0] * (N + 1)
    for i in range(N):
        prefix_sum[i + 1] = prefix_sum[i] + A[i]
    
    min_prod = float('inf')
    max_prod = float('-inf')
    
    for _ in range(M):
        L, R = map(int, input().split())
        # 区画の生産力を計算（L, Rは1-indexed）
        prod = prefix_sum[R] - prefix_sum[L - 1]
        min_prod = min(min_prod, prod)
        max_prod = max(max_prod, prod)
    
    print(max_prod - min_prod)

if __name__ == "__main__":
    main()

---

この解説は claude4.5opus によって生成されました。