概要

与えられた区画分けに対し、各区画の生産力（収穫量の合計）の最大値と最小値の差を求める問題。

考察

各区画は連続した畑から構成されており、各区画の生産力はその区間に含まれる畑の収穫量の合計となる。
素朴な方法では、各区画ごとに \(L_j\) から \(R_j\) までループを回して合計を求めると、最悪ケースで \(O(N \times M)\) の計算が必要となり、制約が \(N, M \sim 2 \times 10^5\) なので時間内に処理しきれない可能性がある（TLE）。

これを解決するために、「累積和」を用いる。
あらかじめ \(S[i] = A_1 + A_2 + \cdots + A_{i-1}\) という累積和配列を作っておくことで、任意の区間 \([L, R]\) の合計が \(S[R] - S[L-1]\) で \(O(1)\) で求められる。
これにより全体の計算量を \(O(N + M)\) に抑えることができる。

アルゴリズム

1. 入力を高速に読み込む（sys.stdin.read を使用）。
2. 畑の収穫量の累積和配列 \(S\) を構築する：
   • \(S[0] = 0\)
   • \(S[i] = S[i-1] + A[i-1]\)
3. 各区画について、\(L_j\) から \(R_j\) の区間和を累積和を使って求める：
   • 区画の生産力 = \(S[R_j] - S[L_j - 1]\)
4. 生産力の最大値と最小値を記録しながら更新していく。
5. 最後に最大値と最小値の差を出力する。

例

例えば、\(A = [10, 20, 30, 40]\) で区画が \([1,2]\) と \([3,4]\) の場合： - 累積和: \(S = [0, 10, 30, 60, 100]\) - 区画1の生産力: \(S[2] - S[0] = 30 - 0 = 30\) - 区画2の生産力: \(S[4] - S[2] = 100 - 30 = 70\) - 差: \(70 - 30 = 40\)

計算量

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

実装のポイント

• sys.stdin.read を使って高速に入力を読み込む（Python では重要）
• 累積和のインデックスに注意（\(S[0] = 0\)、\(A[i]\) に対応するのが \(S[i+1]\)）
• 最大・最小の初期値に注意（最大は十分小さな値、最小は十分大きな値で初期化）

## ソースコード

```python
import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    M = int(data[1])
    A = list(map(int, data[2:2+N]))
    
    # 累積和を計算
    S = [0] * (N + 1)
    for i in range(N):
        S[i+1] = S[i] + A[i]
    
    max_prod = -1
    min_prod = float('inf')
    
    idx = 2 + N
    for _ in range(M):
        L = int(data[idx])
        R = int(data[idx+1])
        idx += 2
        prod = S[R] - S[L-1]
        if prod > max_prod:
            max_prod = prod
        if prod < min_prod:
            min_prod = prod
    
    print(max_prod - min_prod)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。