概要

\(M\) 個の区間が与えられたとき、少なくとも1つの区間に含まれる区画の果物の量の総和を求める問題です。いもす法を使って効率的に解くことができます。

考察

問題の本質

同じ区画で複数回収穫しても、収穫量は1回分しかカウントされません。つまり、各区画について「1回以上収穫されたかどうか」だけが重要です。

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

愚直に考えると、各収穫作業ごとに区画 \(L_j\) から \(R_j\) まで1つずつチェックする方法があります。

for 各収穫作業 j:
    for i = L_j to R_j:
        区画iを「収穫済み」にする

しかし、この方法では最悪の場合、1回の収穫作業で \(O(N)\) 個の区画を処理するため、全体で \(O(N \times M)\) の計算量となります。\(N, M\) が最大 \(2 \times 10^5\) のとき、\(4 \times 10^{10}\) 回の処理が必要となり、TLE（時間制限超過）になります。

解決のアイデア

「各区画が何回収穫作業の対象になったか」を効率的に計算できれば、1回以上なら収穫量を加算すればよいです。この「区間への加算」を高速に行うためにいもす法を使います。

アルゴリズム

いもす法とは

区間 \([L, R]\) に対する加算を、差分配列を使って \(O(1)\) で処理する手法です。

手順： 1. 差分配列 diff を用意 2. 区間 \([L, R]\) への +1 を、diff[L] += 1 と diff[R+1] -= 1 で表現 3. 最後に累積和を取ると、各位置での値が得られる

具体例

\(N = 5\) で、区間 \([2, 4]\) と \([3, 5]\) に +1 する場合：

初期:   diff = [0, 0, 0, 0, 0, 0, 0]  (インデックス0〜6)

[2,4]: diff[2]+=1, diff[5]-=1 → [0, 0, 1, 0, 0, -1, 0]
[3,5]: diff[3]+=1, diff[6]-=1 → [0, 0, 1, 1, 0, -1, -1]

累積和を取ると:
位置1: 0
位置2: 0+1 = 1
位置3: 1+1 = 2
位置4: 2+0 = 2
位置5: 2-1 = 1

結果：区画2,3,4,5が1回以上収穫される（値 > 0）

本問題への適用

1. 全ての収穫作業 \((L_j, R_j)\) について、差分配列に記録
2. 累積和を取りながら、各区画のカウントが 0 より大きければ \(A_i\) を総収穫量に加算

計算量

• 時間計算量: \(O(N + M)\)
  • \(M\) 回の区間登録：各 \(O(1)\) で合計 \(O(M)\)
  • \(N\) 個の区画の累積和計算と集計：\(O(N)\)
• 空間計算量: \(O(N)\)
  • 差分配列のサイズ

実装のポイント

• 差分配列のサイズは \(N + 2\) にすると、diff[R + 1] でインデックスが範囲外にならず安全です

• 区画番号は 1-indexed、配列 \(A\) は 0-indexed なので、A[i - 1] でアクセスする点に注意

• 収穫量の総和は最大 \(N \times \max(A_i) = 2 \times 10^5 \times 10^9 = 2 \times 10^{14}\) になりうるので、64bit整数（Pythonでは自動）で扱う必要があります

  ソースコード

def main():
    import sys
    input = sys.stdin.readline
    
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    
    # 区間和クエリのために、どの区画が収穫されたかを管理する
    # いもす法を使って、各区画が少なくとも1回収穫されるかどうかを判定
    
    # 差分配列を使用
    diff = [0] * (N + 2)
    
    for _ in range(M):
        L, R = map(int, input().split())
        diff[L] += 1
        diff[R + 1] -= 1
    
    # 累積和を取って、各区画が収穫されたかどうかを判定
    total = 0
    count = 0
    for i in range(1, N + 1):
        count += diff[i]
        if count > 0:
            total += A[i - 1]
    
    print(total)

if __name__ == "__main__":
    main()

---

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