概要

複数の区間収穫をすべて行ったとき、少なくとも1回でも収穫対象になった区画の \(A_i\) を合計すればよい問題です。

考察

各収穫作業 \((L_j, R_j)\) は「この区間に含まれる区画は収穫される（ただし同じ区画は1回しか数えない）」という操作です。
つまり最終的に知りたいのは、

• 区画 \(i\) が 1回以上 どれかの区間に含まれたか（収穫されたか）
• 含まれたなら \(A_i\) を足す、含まれないなら足さない

という判定だけです。何回含まれたかは不要です（1回でも含まれれば \(A_i\) を1回足すだけ）。

素朴な方法がダメな理由

各クエリ \((L, R)\) ごとに区間内の全マスを「収穫済み」にするような実装をすると、最悪で

• \(M=2\times 10^5\) 回
• 各回で最大 \(N=2\times 10^5\) 個の区画をなめる

となり、\(O(NM)\) で最大約 \(4\times 10^{10}\) 操作になって間に合いません（TLE）。

解決方針

「区間に1以上の被覆があるか」を高速に求めたいので、典型的な 差分配列（いもす法） を使います。

• 区間 \([L, R]\) を「+1」する操作を、差分配列で
  • diff[L] += 1
  • diff[R+1] -= 1 と記録しておく
• 最後に前から累積和を取ると、各区画が何回区間に含まれたか（被覆回数）が \(O(N)\) で分かる
• 被覆回数が \(>0\) なら収穫されるので \(A_i\) を足す

例えば \(N=5\)、区間が \([2,4]\) と \([3,5]\) なら、累積後の被覆回数は - \(i=1\):0, \(i=2\):1, \(i=3\):2, \(i=4\):2, \(i=5\):1 となり、\(2\sim 5\) の \(A_i\) を合計すれば答えです。

アルゴリズム

1. 配列 diff を長さ \(N+2\) 程度で用意し、すべて \(0\) で初期化する。
2. 各収穫作業 \((L, R)\) について
   • diff[L] += 1
   • diff[R+1] -= 1 を行う。
3. \(i=1\) から \(N\) まで順に累積和 cur += diff[i] を計算する。
4. cur > 0（区画 \(i\) が1回以上収穫対象）なら total += A[i] を加算する。
5. total を出力する。

計算量

• 時間計算量: \(O(N+M)\)（差分更新が \(O(M)\)、累積と合計が \(O(N)\)）
• 空間計算量: \(O(N)\)（差分配列と \(A\)）

実装のポイント

• 差分配列では diff[R+1] にアクセスするため、配列サイズを \(N+2\) 以上にする（コードでは安全に N+3）。

• Python では入力が大きいので sys.stdin.buffer.read() で一括読み込みすると高速です。

• \(A_i\) は \(10^9\)、\(N\) は \(2\times 10^5\) なので合計は最大 \(2\times 10^{14}\) 程度になり、Python の int なら問題ありません。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    M = next(it)
    A = [0] + [next(it) for _ in range(N)]  # 1-indexed

    diff = [0] * (N + 3)
    for _ in range(M):
        l = next(it)
        r = next(it)
        diff[l] += 1
        diff[r + 1] -= 1

    cur = 0
    total = 0
    for i in range(1, N + 1):
        cur += diff[i]
        if cur > 0:
            total += A[i]

    print(total)

if __name__ == "__main__":
    main()

---

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