Overview

Simulating the repainting operations from the front in order is too slow, so the key is to process them in reverse order from the back.
Additionally, to efficiently skip over boards whose final color has already been determined, we use a data structure similar to Union-Find that “finds the next undetermined position”.

Analysis

In this problem, intervals \([L_i, R_i]\) are repeatedly overwritten with color \(C_i\).
Since we want “the color that remains at the end,” what matters is the last operation that painted each board.

Naive Approach

Suppose we repaint all boards in the interval for each operation.

• A single operation can paint up to \(N\) boards
• There are up to \(M\) operations

Therefore, the worst-case complexity is \(O(NM)\).
Given the constraints:

• \(N \le 5 \times 10^5\)
• \(M \le 2 \times 10^5\)

the worst case involves on the order of \(10^{11}\) updates, which is clearly too slow.

---

Key Insight: Viewing from the back, the “first color painted” is the answer

For example, suppose the sequence of operations is:

1. Paint \([2,5]\) with color 3
2. Paint \([4,7]\) with color 8
3. Paint \([1,3]\) with color 2

Viewing from the front, things get complicated due to repeated overwrites, but viewing from the back changes the situation.

• Looking at operation 3: boards \(1,2,3\) have not yet been determined, so their final color is set to 2
• Next, looking at operation 2: among boards \(4,5,6,7\), only the undetermined ones get their final color set to 8
• Finally, looking at operation 1: boards \(2,3,4,5\) are already determined, so they can be ignored

In other words, when processing in reverse order, each board’s final color is determined by the first operation it encounters.

---

Even so, scanning the interval each time is slow

Even in reverse order, if for each operation we iterate from \(L_i\) to \(R_i\):

• Paint if still undetermined
• Skip if already determined

we may still visit many positions multiple times, which is still slow.

---

How to speed it up

We prepare a mechanism to quickly find “the next undetermined board”.

We use parent[x] to
find the leftmost position at or after position \(x\) whose color has not yet been determined.

Once the color of board \(x\) is determined, we never need to visit it again.
Therefore:

• After determining board \(x\)
• Set parent[x] = find(x + 1)

This encodes the information: “position \(x\) is already processed, so next time look at \(x+1\) or beyond.”

With this method, once a board is determined, it is collectively skipped in all subsequent operations.
Since each board is determined at most once, the overall process is very fast.

Algorithm

The approach used is reverse-order processing + Union-Find (Disjoint Set Union)-style skipping.

Data Structures

• ans[i]: the final color of board \(i\)
• parent[i]: an array for finding “the leftmost undetermined position at or after \(i\)”
• find(x): a function that finds the representative with path compression

In the initial state, no board has been determined, so:

• parent[i] = i

We also prepare a sentinel at N+1 to make it easy to check when we’ve exceeded the right end of an interval.

---

Procedure

1. Store all operations in an array
2. Process operations from back to front
3. For operation \((L_i, R_i, C_i)\):
   • Use p = find(L_i) to find the first undetermined position within the interval
   • While p <= R_i:
     • Set ans[p] = C_i to determine the color
     • Since this position is no longer needed, set parent[p] = find(p + 1)
     • Move to the next undetermined position
4. Finally, output ans[1] through ans[N]

---

Concrete Example

Suppose \(N=8\) and the operations are as follows:

1. \([2,6] \leftarrow 5\)
2. \([4,8] \leftarrow 7\)
3. \([3,5] \leftarrow 2\)

We process in reverse order.

Operation 3: \([3,5] \leftarrow 2\)

Boards 3, 4, 5 are undetermined, so set them to color 2.

Operation 2: \([4,8] \leftarrow 7\)

Boards 4, 5 are already determined, so skip them.
Set boards 6, 7, 8 to color 7.

Operation 1: \([2,6] \leftarrow 5\)

Boards 3, 4, 5, 6 are already determined, so skip them.
Only board 2 is set to color 5.

The final result is:

• 1: 0
• 2: 5
• 3, 4, 5: 2
• 6, 7, 8: 7

As shown, skipping already-determined positions at once using Union-Find is the core idea.

Complexity

• Time complexity: \(O((N + M)\alpha(N))\)
• Space complexity: \(O(N + M)\)

Here, \(\alpha(N)\) is the inverse Ackermann function, which is practically constant.
Intuitively, since each board is determined exactly once, the algorithm is very fast.

Implementation Notes

• Operations are processed from the back, not the front
• find(x) is used to find “the next undetermined position”
• After determining board p, set parent[p] = find(p + 1) so it will be skipped from then on
• Preparing N+1 as a sentinel makes the p <= R check straightforward
• The provided code uses array('I'), which is more memory-efficient than a regular Python list for large inputs

The essence of this implementation is that Union-Find is not used for “connectivity checks,” but rather as a data structure for quickly finding the next unprocessed position.

Source Code

import sys
from array import array

input = sys.stdin.buffer.readline

N, M = map(int, input().split())

L = array('I')
R = array('I')
C = array('I')

for _ in range(M):
    l, r, c = map(int, input().split())
    L.append(l)
    R.append(r)
    C.append(c)

parent = array('I', range(N + 2))
ans = array('I', [0]) * (N + 1)

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

for i in range(M - 1, -1, -1):
    l = L[i]
    r = R[i]
    c = C[i]
    p = find(l)
    while p <= r:
        ans[p] = c
        nxt = find(p + 1)
        parent[p] = nxt
        p = nxt

sys.stdout.write(' '.join(map(str, ans[1:])))

---

This editorial was generated by gpt-5.4-high.