Overview

Given \(N\) boards, we perform \(M\) interval repainting operations in order and determine the final color of each board. Since later paint overwrites earlier paint, each board’s color is determined by “the last operation that painted it.”

Analysis

Problem with the Naive Approach

The simplest method is to paint boards one by one from \(L_i\) to \(R_i\) for each operation. However, a single operation can paint up to \(N = 5 \times 10^5\) boards, and there are \(M = 2 \times 10^5\) operations, resulting in a worst-case complexity of \(O(NM) = 10^{11}\), which causes TLE (Time Limit Exceeded).

Key Insight: Only “the last painted color” matters

The final color of each board is determined by the color of the last operation that painted it. In other words, even if the same board is painted multiple times, all operations except the last one are wasted.

Using this property, we can process operations in reverse order (from back to front). When processing an operation \([L_i, R_i, C_i]\) in reverse order, we only need to assign color \(C_i\) to boards whose color has not yet been determined (i.e., boards not yet assigned to any operation). Once a board’s color is determined, it can be ignored for all subsequent operations (which are earlier operations in the original order).

Problem: How to efficiently find unpainted boards?

In the reverse-order processing, we want to find unpainted boards within the interval \([L_i, R_i]\), but checking one by one could still result in \(O(NM)\). Here we use the path compression technique of Union-Find (disjoint set data structure).

Algorithm

Union-Find for Managing “Next Unpainted Position”

We prepare an array parent[i] that manages “the nearest unpainted board number at position \(i\) or later.”

• Initial state: parent[i] = i (all boards are unpainted, so each position points to itself)
• When board \(i\) is painted: Set parent[i] = i + 1 (position \(i\) is now painted, so the next unpainted position is \(i+1\) or later)
• find(x): Follows parent with path compression and returns the first unpainted position at or after position \(x\)

Processing Flow

1. Process operations in reverse order (\(i = M, M-1, \ldots, 1\))
2. For operation \([L_i, R_i, C_i]\), get the first unpainted position in the interval with pos = find(L_i)
3. While pos <= R_i, assign color \(C_i\) to board pos, set parent[pos] = pos + 1, and move to the next
4. After processing all operations, boards that were not assigned any color remain at their initial value \(0\)

Concrete Example

For \(N = 5, M = 2\), operation 1: \([1, 4, 3]\), operation 2: \([2, 5, 7]\):

• Process operation 2 in reverse: Assign color 7 to boards 2, 3, 4, 5 → boards = [0, 7, 7, 7, 7]
• Process operation 1 in reverse: Search for unpainted boards in \([1,4]\) → only board 1 is unpainted → assign color 3 to board 1
• Final result: 3 7 7 7 7

Complexity

• Time complexity: \(O(N + M \cdot \alpha(N))\) (\(\alpha\) is the inverse Ackermann function, which is effectively constant. Since each board is painted at most once, the total number of paintings across all operations is \(O(N)\))
• Space complexity: \(O(N + M)\)

Implementation Notes

• The parent array should have size \(N+2\). parent[N+1] serves as a sentinel, so when find returns \(N+1\), we know we are outside the interval

• In Python, recursive find risks stack overflow, so it is implemented using a loop with path compression (path halving) (parent[x] = parent[parent[x]])

• Input is read all at once using sys.stdin.buffer.read() for faster I/O

  Source Code

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    boards = [0] * (N + 1)
    
    # Process operations in reverse order; skip already painted positions
    # Use a set or interval structure to track unpainted positions
    # We'll use a sorted set approach with an interval list
    
    # We maintain a list of "free" intervals (not yet assigned)
    # Initially all [1, N] is free
    # Process from last operation to first; for each operation [L, R, C],
    # find all free positions in [L, R], assign them C, and remove them from free set.
    
    # Use a simple approach with a "next unpainted" array (like DSU/path compression)
    # parent[i] points to the next unpainted position >= i
    
    parent = list(range(N + 2))  # parent[i] for i in 0..N+1
    
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    
    operations = []
    for i in range(M):
        L = int(input_data[idx]); idx += 1
        R = int(input_data[idx]); idx += 1
        C = int(input_data[idx]); idx += 1
        operations.append((L, R, C))
    
    # Process in reverse
    for i in range(M - 1, -1, -1):
        L, R, C = operations[i]
        pos = find(L)
        while pos <= R:
            boards[pos] = C
            parent[pos] = pos + 1  # mark as painted, point to next
            pos = find(pos + 1)
    
    sys.stdout.write(' '.join(map(str, boards[1:N+1])) + '\n')

main()

---

This editorial was generated by claude4.6opus-thinking.