Overview

Simulating the repainting operations in order as-is is too slow, so we solve this efficiently by processing operations in reverse order and “painting only the boards whose color has not yet been determined, exactly once.” To quickly skip to the next undetermined position, we use a Union-Find structure (for managing the next unprocessed position).

Key Observations

The two important observations are:

1. The final color of a board is determined by “the last operation that painted that board.”
2. Therefore, if we look at operations from the back, the first color encountered for a board becomes its final color.

Naively painting the entire interval \([L_i, R_i]\) for each operation results in a worst case of \(M \times N \approx 2\times10^5 \times 5\times10^5\), which is far too slow.

When thinking in reverse order, “boards whose color is already determined” no longer need to be touched. So if we can quickly find “the first undetermined board at position \(x\) or greater,” we can skip over already-determined intervals all at once.

This “jump to the next undetermined position” is realized by the Union-Find-like array parent used here. parent[x] points to “the next candidate to look at if \(x\) is already determined,” and find(x) retrieves the representative (the actual undetermined position).

Algorithm

1. Initialize ans[1..N] = 0 (unpainted).
2. Prepare parent[i] = i, and also create a sentinel at N+1.
3. Process the operations in reverse order:
   • For operation \((l, r, c)\), set x = find(l)
   • While x <= r:
     • ans[x] = c (the final color of this board is now determined)
     • Set parent[x] = find(x+1) so that x will be skipped from now on
     • Advance to the next undetermined board with x = parent[x]
4. Finally, output ans[1..N].

Illustration

For example, while processing interval \([2,5]\) in reverse order, if boards 3 and 4 are already determined, then after find(2), we can jump directly to 5 or 6. Since each board is processed only once when it becomes determined, this is fast.

Complexity

• Time complexity: \(O((N+M)\alpha(N))\) (nearly linear)
• Space complexity: \(O(N+M)\) (ops, parent, ans)

Implementation Notes

• Create parent with length N+2, using N+1 as a sentinel (to prevent out-of-bounds access).

• Adding path compression to find speeds it up (in the code, this is done with a while loop + compression).

• Reverse-order processing is the key insight. Trying to do the same thing in forward order becomes difficult.

• When \(M=0\), ans is correctly all 0s and is output as-is.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    ops = [tuple(map(int, input().split())) for _ in range(M)]

    parent = list(range(N + 2))  # 1..N, sentinel N+1
    ans = [0] * (N + 1)

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    for l, r, c in reversed(ops):
        x = find(l)
        while x <= r:
            ans[x] = c
            parent[x] = find(x + 1)
            x = parent[x]

    print(*ans[1:])

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.3-codex.