概要

各区画（連続区間）に含まれる収穫量の合計を求め、区画合計の最大値と最小値の差を出力する問題です。

考察

区画 \([L_j, R_j]\) の生産力は \(A_{L_j}+A_{L_j+1}+\cdots+A_{R_j}\) です。
これを各区画ごとに素朴に足し合わせると、最悪の場合（例えば \(M=N\) で各区画が長い）に合計で \(O(NM)\) 近くかかり、\(N \le 2\times 10^5\) では間に合いません。

ここで重要な気づきは、「区間和」は累積和（prefix sum）で高速に求められることです。

累積和 \(pref[i] = A_1 + A_2 + \cdots + A_i\) を用意すると、区間和は

• \(sum(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\) と一発で求まります。

この方法で各区画の和を順に計算しながら、最小値 \(mn\) と最大値 \(mx\) を更新していけば、最後に \(mx-mn\) が答えになります。

アルゴリズム

1. 配列 \(A\) の累積和配列 \(pref\) を作る。
   
   • \(pref[0]=0\)
   • \(pref[i]=pref[i-1]+A_i\)
2. 各区画入力 \((L, R)\) について区間和 \(seg = pref[R] - pref[L-1]\) を計算する。
3. \(seg\) の最小値 \(mn\) と最大値 \(mx\) を更新する。
4. 最後に \(mx - mn\) を出力する。

計算量

• 時間計算量: \(O(N + M)\)（累積和構築が \(O(N)\)、各区画処理が \(O(M)\)）
• 空間計算量: \(O(N)\)（累積和配列）

実装のポイント

• \(pref[L-1]\) を使うため、\(pref[0]=0\) を用意し、配列を 1-indexed にすると実装が楽です。

• 収穫量や区間和は最大で \(10^9 \times 2\times 10^5\) 程度になり得るため、Python なら問題ありませんが、他言語では 64bit 整数が必要です。

• 入力が大きいので、コードのように sys.stdin.buffer.read() で高速に読み取ると安全です。

  ソースコード

import sys

def main():
    it = iter(map(int, sys.stdin.buffer.read().split()))
    N = next(it)
    M = next(it)

    A = [0] * (N + 1)
    for i in range(1, N + 1):
        A[i] = next(it)

    pref = [0] * (N + 1)
    s = 0
    for i in range(1, N + 1):
        s += A[i]
        pref[i] = s

    mn = None
    mx = None
    for _ in range(M):
        L = next(it)
        R = next(it)
        seg = pref[R] - pref[L - 1]
        if mn is None or seg < mn:
            mn = seg
        if mx is None or seg > mx:
            mx = seg

    print(mx - mn)

if __name__ == "__main__":
    main()

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