概要

各区画から収穫できる果物の量が与えられ、複数の区間に対して収穫作業を行うとき、得られる果物の総量を求める問題です。ただし、各区画からは一度しか収穫できません。

考察

この問題では、各区画が何回以上の収穫作業で被覆されているかを効率的に求め、一度でも被覆されていればその区画の果物を加算する必要があります。

素朴なアプローチ（TLEとなってしまうもの）

例えば、各区間 \([L_j, R_j]\) に対して、愚直にフラグを立てていき、「この区画は既に収穫済みか」を管理する配列を使う方法があります。しかし、区間の長さが最大 \(N\)、操作回数も最大 \(M\) となるため、最悪計算量は \(O(N \times M)\) となり、\(N, M \sim 2 \times 10^5\) では到底間に合いません。

改善策：imos法 + 座標圧縮

このような「区間に対する加算クエリ」と「最終的な値の取得」というタイプの問題には、imos法（いもす法）が非常に有効です。

しかし、今回の問題では区間が非常に広く、すべての区画に対してimos法を適用するとメモリや時間的に厳しくなります。そこで、座標圧縮を組み合わせることで、実際に登場する区間の端点だけを扱うようにします。

具体的には： 1. 各収穫区間の始点と終点+1にイベントを設定します。 2. それらのイベントの座標を集めてソートし、重複を除いて座標圧縮します。 3. 圧縮後の座標に対してimos法を行い、各区間が何回被覆されているかを求めます。 4. 被覆回数が1以上である区間に対応する元の果物の量を加算します。

これにより、無駄な計算を省き、効率的に答えを求めることができます。

アルゴリズム

1. 入力を読み込み、各区画の果物の量 \(A_i\) をリストに格納します。
2. 各収穫区間 \([L_j, R_j]\) に対して、
   • 開始点 \(L_j - 1\)（0-indexedへ変換）に +1、
   • 終了点の次 \(R_j\) に -1 のイベントを記録します。
3. 登場したすべてのイベントの座標を集め、重複を除去・ソートして座標圧縮します。
4. imos法を用いて、圧縮された座標上で各区間の被覆回数を計算します。
5. 被覆回数が1以上である区間について、元の配列 \(A\) の該当部分の和を答えに加算します。

例

例えば、\(N = 5\), \(A = [10, 20, 30, 40, 50]\) で、区間が \([1,3], [2,4]\) だったとします。

• イベントは \((0,+1), (3,-1), (1,+1), (4,-1)\)
• 座標を圧縮すると、\([0,1,3,4]\)
• imos法でカウントすると、区間 \([0,1)\) は1回、\([1,3)\) は2回、\([3,4)\) は1回被覆
• 対応する果物の和：\(A[0..1] + A[1..3] + A[3..4] = 10 + (20+30) + 40 = 100\)

計算量

• 時間計算量: \(O((N + M) \log (N + M))\)
  • イベントのソートと座標圧縮が支配的
• 空間計算量: \(O(N + M)\)

実装のポイント

• 区間は1-indexedで与えられるので、内部処理では0-indexedに変換する

• imos法の適用時は、イベントの位置に注意（終了は R+1）

• 座標圧縮後の区間の果物の和を計算する際、元の配列の添字に注意

  ソースコード

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]))
    
    # 区間を処理するためのイベントリストを作成
    events = []
    index = 2 + N
    for _ in range(M):
        L = int(data[index]) - 1  # 0-indexedにする
        R = int(data[index+1]) - 1
        events.append((L, 1))      # 区間開始
        events.append((R+1, -1))   # 区間終了
        index += 2
    
    # 座標圧縮の準備
    coords = sorted(set([e[0] for e in events] + [N]))
    coord_map = {v: i for i, v in enumerate(coords)}
    
    # imos法で各区間の被覆回数を計算
    count = [0] * (len(coords) + 1)
    for pos, delta in events:
        count[coord_map[pos]] += delta
    
    # 累積和を計算して各区間の被覆回数を得る
    for i in range(1, len(count)):
        count[i] += count[i-1]
    
    # 各区画が何回被覆されているかを確認し、1回以上なら加算
    total = 0
    for i in range(len(coords)-1):
        if count[i] > 0:
            left = coords[i]
            right = coords[i+1]
            # A[left:right] の和を計算
            total += sum(A[left:right])
    
    print(total)

if __name__ == "__main__":
    main()

---

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