Overview

This problem asks you to perform \(M\) operations, each adding \(+1\) uniformly to an interval \([L_i, R_i]\), and then efficiently compute the final value at each position.

Analysis

A naive approach would update all elements within the interval for each operation. That is, operation \(i\) performs \(R_i - L_i + 1\) additions, so in the worst case: - \(N = 2 \times 10^5\), \(M = 2 \times 10^5\) - Each operation covers nearly the entire range (length \(N\))

The number of updates would be \(O(NM)\), reaching approximately \(4 \times 10^{10}\), which is far too slow (TLE).

The key insight here is that for operations that “add the same value to an entire interval,” instead of directly updating each element, we can record only the endpoints of the interval and reconstruct the values all at once at the end.

As a concrete example, with \(N=5\) and an operation on \([2, 4]\), the final result should be: - Only the range 2 through 4 gets \(+1\)

So we think of it as: - At position 2, the \(+1\) “begins” - At position 5 (= 4 + 1), the \(+1\) “ends”

By marking these endpoints and then accumulating from left to right at the end, we can determine the value at each position.

Algorithm

We use a difference array (imos method / prefix sum).

1. Prepare an array diff of length approximately \(N+2\), initialized entirely to 0.
2. For each operation \((L, R)\), do the following:
   • diff[L] += 1 (the addition starts at \(L\))
   • diff[R+1] -= 1 (the addition ends at \(R+1\))
3. Finally, for \(i = 1..N\), compute the prefix sum cur += diff[i], and cur directly gives the final value at position \(i\).

This transforms “range addition” into “two updates at the endpoints,” then reconstructs the result using a prefix sum at the end.

Complexity

• Time complexity: \(O(N+M)\) (each operation is \(O(1)\), and the final reconstruction is \(O(N)\))
• Space complexity: \(O(N)\) (for the difference array and the output array)

Implementation Notes

• Since we access diff[R+1], the array must be allocated with size at least \(N+2\) (the code safely uses \(N+3\)).

• Since the input can consist of up to approximately \(4 \times 10^5\) integers, reading all at once with sys.stdin.buffer.read() is faster.

• Outputting everything at once using join is also fast enough even in Python.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, M = data[0], data[1]
    diff = [0] * (N + 3)

    idx = 2
    for _ in range(M):
        L = data[idx]
        R = data[idx + 1]
        idx += 2
        diff[L] += 1
        diff[R + 1] -= 1

    cur = 0
    ans = []
    for i in range(1, N + 1):
        cur += diff[i]
        ans.append(str(cur))

    sys.stdout.write(" ".join(ans))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.