概要

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

考察

この問題の核となるのは、「指定された範囲の合計値をいかに効率よく求めるか」という点です。

1. 素朴な方法とその限界

各区画の合計を求めるために、毎回 \(L_j\) から \(R_j\) までループを回して足し算を行うとどうなるでしょうか。 最悪の場合、1つの区画の長さが \(N\) に近くなるため、1回の計算に \(O(N)\) かかります。区画は \(M\) 個あるため、全体の計算量は \(O(N \times M)\) となります。 本問題の制約では \(N, M \leq 2 \times 10^5\) であるため、最大で \(4 \times 10^{10}\) 回程度の計算が必要になり、実行時間制限（通常 2秒程度）に間に合いません。

2. 累積和による高速化

連続する範囲の合計を高速に求める手法として累積和（Prefix Sum）が有効です。 あらかじめ、最初の畑から各地点までの合計値を計算しておきます。 - \(P_0 = 0\) - \(P_1 = A_1\) - \(P_2 = A_1 + A_2\) - \(P_i = A_1 + A_2 + \dots + A_i\)

このように準備しておくと、畑 \(L\) から畑 \(R\) までの合計は、以下の式で \(O(1)\) で計算できます。 $\(\text{合計} = P_R - P_{L-1}\)$ これにより、大量の区画があっても高速に処理することが可能になります。

アルゴリズム

1. 累積和の構築: 畑の収穫量 \(A_i\) を順に読み込み、累積和の配列 \(P\) を作成します。
2. 各区画の計算: 与えられた \(M\) 個の範囲 \((L_j, R_j)\) について、累積和を用いてその区画の生産力を計算します。
3. 最大・最小の更新: 計算した生産力を順次比較し、全体の最大値 max_prod と最小値 min_prod を記録します。
4. 結果の出力: max_prod - min_prod を計算して出力します。

計算量

• 時間計算量: \(O(N + M)\)
  • 累積和の構築に \(O(N)\)、各区画の計算（\(M\) 回）に \(O(M)\) かかります。入力の読み込みを含めても線形時間で処理可能です。
• 空間計算量: \(O(N)\)
  • 収穫量データと累積和配列を保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入出力: \(N\) や \(M\) が大きいため、Python では sys.stdin.read().split() を使って一括で入力を読み込むことで、実行時間を大幅に短縮できます。

• インデックスの調整: 畑の番号は \(1\) から始まる（1-indexed）ため、累積和の配列 \(P\) のサイズを \(N+1\) にし、先頭に \(0\) を入れることで、範囲計算 \(P_R - P_{L-1}\) をミスなく実装できます。

• 初期値の設定: 最小値の初期化には、十分に大きな値（float('inf') など）を使用してください。

  ソースコード

import sys
from itertools import accumulate

def solve():
    # 標準入力からすべてのデータを一括で読み込み、空白で分割します。
    # これは大規模な入力（N, M = 2 * 10^5）を高速に処理するための一般的な手法です。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 読み込んだ文字列のリストを整数のリストに変換します。
    data = list(map(int, input_data))
    
    # 最初の2つの値は N（畑の数）と M（区画の数）です。
    N = data[0]
    M = data[1]
    
    # 畑の収穫量 A_1 から A_N は、data[2] から data[N+1] に格納されています。
    # 累積和（Prefix Sum）を計算して、任意の区間の合計を O(1) で求められるようにします。
    # P[i] は 畑 1 から 畑 i までの収穫量の合計を保持します。
    # P[0] = 0, P[1] = A_1, P[2] = A_1 + A_2, ..., P[N] = sum(A_1...A_N)
    P = [0] + list(accumulate(data[2:N+2]))
    
    # 各区画の生産力の最大値と最小値を追跡するための変数を初期化します。
    # 収穫量 A_i は 1 以上なので、生産力の最小値は非常に大きな値で、最大値は -1 で初期化します。
    max_prod = -1
    min_prod = float('inf')
    
    # 各区画の範囲 (L_j, R_j) は、data[N+2] 以降に順番に格納されています。
    # イテレータを使用して、L と R をペアで取り出します。
    it = iter(data[N+2:])
    for _ in range(M):
        # L と R は 1-indexed の畑番号です。
        try:
            L = next(it)
            R = next(it)
        except StopIteration:
            break
        
        # 畑 L から 畑 R までの生産力（収穫量の合計）は、累積和を使って
        # P[R] - P[L-1] で計算できます。
        current_sum = P[R] - P[L-1]
        
        # 最大値と最小値を更新します。
        if current_sum > max_prod:
            max_prod = current_sum
        if current_sum < min_prod:
            min_prod = current_sum
            
    # 最も生産力の高い区画と最も低い区画の差を出力します。
    if max_prod == -1:
        # M=0 の場合は問題の制約上発生しませんが、念のため 0 を出力します。
        print(0)
    else:
        print(max_prod - min_prod)

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-preview によって生成されました。