Overview

This is a problem where, after performing all the interval harvests, you need to sum up \(A_i\) for every plot that was harvested at least once.

Analysis

Each harvest operation \((L_j, R_j)\) is an operation that says “the plots contained in this interval are harvested (but the same plot is only counted once).” In other words, what we ultimately want to know is:

• Whether plot \(i\) was included in at least one interval (i.e., whether it was harvested)
• If included, add \(A_i\); if not, don’t add it

It’s just this determination. We don’t need to know how many times it was included (even if included once, we only add \(A_i\) once).

Why the naive approach doesn’t work

If we implement it by marking all cells in the interval as “harvested” for each query \((L, R)\), in the worst case:

• \(M = 2 \times 10^5\) operations
• Each operation iterates over up to \(N = 2 \times 10^5\) plots

This results in \(O(NM)\), which is approximately \(4 \times 10^{10}\) operations at maximum, and will not finish in time (TLE).

Solution approach

Since we want to efficiently determine “whether each position has coverage of 1 or more,” we use the classic difference array (imos method).

• For each interval \([L, R]\) “+1” operation, record it in the difference array as:
  • diff[L] += 1
  • diff[R+1] -= 1
• Finally, take the prefix sum from the beginning to determine the coverage count for each plot in \(O(N)\)
• If the coverage count is \(> 0\), the plot is harvested, so add \(A_i\)

For example, if \(N=5\) and the intervals are \([2,4]\) and \([3,5]\), the coverage counts after taking the prefix sum are: - \(i=1\): 0, \(i=2\): 1, \(i=3\): 2, \(i=4\): 2, \(i=5\): 1

So summing \(A_i\) for \(2 \sim 5\) gives the answer.

Algorithm

1. Prepare an array diff of length approximately \(N+2\), initialized to all \(0\).
2. For each harvest operation \((L, R)\):
   • diff[L] += 1
   • diff[R+1] -= 1
3. Compute the prefix sum cur += diff[i] sequentially for \(i = 1\) to \(N\).
4. If cur > 0 (plot \(i\) is a harvest target at least once), add total += A[i].
5. Output total.

Complexity

• Time complexity: \(O(N+M)\) (difference array updates are \(O(M)\), prefix sum and summation are \(O(N)\))
• Space complexity: \(O(N)\) (for the difference array and \(A\))

Implementation notes

• Since the difference array accesses diff[R+1], the array size should be at least \(N+2\) (in the code, we safely use N+3).

• In Python, since the input can be large, reading all at once with sys.stdin.buffer.read() is faster.

• Since \(A_i\) can be up to \(10^9\) and \(N\) up to \(2 \times 10^5\), the total can be approximately \(2 \times 10^{14}\) at maximum, which is no problem with Python’s int.

  Source Code

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

---

This editorial was generated by gpt-5.2-high.