Overview

Given the amount of fruit that can be harvested from each plot, and multiple intervals over which harvesting operations are performed, the problem asks to find the total amount of fruit obtained. However, each plot can only be harvested once.

Analysis

In this problem, we need to efficiently determine how many harvesting operations cover each plot, and if a plot is covered at least once, add its fruit amount to the total.

Naive Approach (Results in TLE)

For example, one could naively set flags for each interval \([L_j, R_j]\) and use an array to track “whether this plot has already been harvested.” However, since the interval length can be up to \(N\) and the number of operations up to \(M\), the worst-case complexity is \(O(N \times M)\), which is far too slow for \(N, M \sim 2 \times 10^5\).

Improvement: imos Method + Coordinate Compression

For this type of problem involving “range addition queries” and “retrieving final values,” the imos method is extremely effective.

However, in this problem the intervals can be very wide, and applying the imos method over all plots would be too costly in terms of memory and time. Therefore, by combining it with coordinate compression, we handle only the endpoints of the intervals that actually appear.

Specifically: 1. Set events at the start point and end point + 1 of each harvesting interval. 2. Collect the coordinates of all these events, sort them, remove duplicates, and perform coordinate compression. 3. Apply the imos method on the compressed coordinates to determine how many times each interval is covered. 4. For intervals with a coverage count of 1 or more, add the corresponding fruit amounts from the original array.

This eliminates unnecessary computation and allows us to find the answer efficiently.

Algorithm

1. Read the input and store the fruit amount \(A_i\) for each plot in a list.
2. For each harvesting interval \([L_j, R_j]\):
   • Record a +1 event at the start point \(L_j - 1\) (converted to 0-indexed),
   • Record a -1 event at the position after the end point \(R_j\).
3. Collect all event coordinates, remove duplicates, sort, and perform coordinate compression.
4. Use the imos method to compute the coverage count for each interval on the compressed coordinates.
5. For intervals with a coverage count of 1 or more, add the sum of the corresponding portion of the original array \(A\) to the answer.

Example

For instance, suppose \(N = 5\), \(A = [10, 20, 30, 40, 50]\), and the intervals are \([1,3], [2,4]\).

• The events are \((0,+1), (3,-1), (1,+1), (4,-1)\)
• After coordinate compression: \([0,1,3,4]\)
• After applying the imos method: interval \([0,1)\) is covered 1 time, \([1,3)\) is covered 2 times, \([3,4)\) is covered 1 time
• The corresponding fruit sums: \(A[0..1] + A[1..3] + A[3..4] = 10 + (20+30) + 40 = 100\)

Complexity

• Time complexity: \(O((N + M) \log (N + M))\)
  • Dominated by sorting events and coordinate compression
• Space complexity: \(O(N + M)\)

Implementation Notes

• Intervals are given in 1-indexed form, so convert to 0-indexed for internal processing

• When applying the imos method, pay attention to event positions (the end is R+1)

• When computing the fruit sum for intervals after coordinate compression, be careful with the indices of the original array

  Source Code

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()

---

This editorial was generated by qwen3-coder-480b.