Overview

Given \(N\) boards, we perform \(M\) interval repainting operations and determine the final color of each board. Since repainting “overwrites” the previous color, the final color of each board is the last color painted on it.

Analysis

Naive Approach

For each query \((L_i, R_i, C_i)\), we could directly update all array elements from \(L_i\) to \(R_i\). However, in the worst case (e.g., every query paints the entire range), the time complexity becomes \(O(N \times M)\). Given the constraints \(N \le 5 \times 10^5, M \le 2 \times 10^5\), this would require up to about \(10^{11}\) operations, which exceeds the time limit.

Thinking in Reverse Order

The key insight of this problem is: “Once a board is painted, whatever color it was painted in earlier operations has no effect on its final color.”

Therefore, we consider processing the painting queries in reverse order (from the \(M\)-th operation backward). 1. The \(M\)-th operation paints the range \([L_M, R_M]\) with color \(C_M\). 2. Next, among the boards not yet painted, those within the range \([L_{M-1}, R_{M-1}]\) of the \((M-1)\)-th operation are painted with color \(C_{M-1}\). 3. Repeat this process down to the 1st operation.

With this approach, once a board has been assigned a color, it can simply be skipped in subsequent processing.

Efficient Skipping Method

To efficiently find “boards not yet painted,” we apply the concept of a Disjoint Set Union (Union-Find / DSU) data structure. We prepare an array parent[i] that holds “the smallest index at or after index i that may still be unpainted.” Immediately after painting board i, we link it to the “next index (i + 1).” This way, the next time we visit the same location, we can use the find function to jump directly to the next unpainted position.

Algorithm

1. Reverse-order processing: Process queries in the order \(i = M, M-1, \dots, 1\).
2. Searching for unpainted sections:
   • Starting from the left endpoint \(L_i\) of the current query, find “the first unpainted board at or after \(L_i\)” using curr = find(L_i).
   • While curr is at most the right endpoint \(R_i\), repeat the following:
     1. Set the color of board curr to \(C_i\).
     2. Since board curr is now painted, link it to the next index by setting parent[curr] = find(curr + 1).
     3. Jump to the next unpainted board with curr = find(curr).
3. Path compression: By rewriting parent pointers inside the find function (path compression), the computation time for each jump is kept nearly constant.

Complexity

• Time complexity: \(O((N + M) \alpha(N))\)
  • Each board transitions from “unpainted” to “painted” exactly once. By utilizing path compression in Union-Find, the jump operations within each query have a very fast amortized complexity (the inverse Ackermann function \(\alpha(N)\)).
• Space complexity: \(O(N + M)\)
  • Memory proportional to \(N\) and \(M\) is used for the array storing board colors, the DSU array, and storing the queries.

Implementation Notes

• Recursion limit: When implementing Union-Find in Python, a recursive find may cause errors at a maximum depth of \(N\) unless sys.setrecursionlimit is configured. As in the code for this problem, using an iterative implementation with a while loop avoids the recursion limit while running efficiently.

• Fast I/O: Since \(N\) and \(M\) are large, we use sys.stdin.read().split() instead of input(), and sys.stdout.write for output, to eliminate I/O bottlenecks.

  Source Code

import sys

# 競技プログラミングの効率的な入出力とロジックを実装します。
# フェンスの塗り替え問題は、後ろから塗り替えを処理することで、
# 各板の最終的な色を効率的に決定できます。

def solve():
    # 標準入力からすべてのデータを取得し、スペース区切りで分割します。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 板の枚数, M: 塗り替えの回数
    N = int(input_data[0])
    M = int(input_data[1])
    
    # 塗り替えの情報をリストに格納します。
    # 後ろから処理するために、L, R, C をそれぞれリストで保持します。
    L = [0] * M
    R = [0] * M
    C = [0] * M
    for i in range(M):
        L[i] = int(input_data[3 * i + 2])
        R[i] = int(input_data[3 * i + 3])
        C[i] = int(input_data[3 * i + 4])
        
    # ans[i] は板 i の最終的な色番号を保持します（1-indexed）。
    ans = [0] * (N + 1)
    
    # すでに色が確定した板をスキップするために、
    # Disjoint Set Union (DSU) の考え方を利用した配列を用意します。
    # parent[i] は、インデックス i 以降でまだ色が確定していない可能性のある最小のインデックスを指します。
    parent = list(range(N + 2))
    
    # DSUのfind操作（経路圧縮あり、反復による実装で再帰制限を回避）
    def find(i):
        root = i
        while parent[root] != root:
            root = parent[root]
        while parent[i] != root:
            next_node = parent[i]
            parent[i] = root
            i = next_node
        return root

    # 塗り替えを後ろ（M回目から1回目）に向かって処理します。
    # ある板が後の操作で塗られた場合、それより前の操作でその板の色が変わることはありません。
    for i in range(M - 1, -1, -1):
        l_idx = L[i]
        r_idx = R[i]
        color = C[i]
        
        # 範囲 [l_idx, r_idx] の中で、まだ色が確定していない板を探します。
        curr = find(l_idx)
        while curr <= r_idx:
            # まだ色が確定していない板に現在の色を割り当てます。
            ans[curr] = color
            # この板の色は確定したので、次のインデックスへリンクさせます。
            parent[curr] = find(curr + 1)
            # 次の未確定の板へ移動します。
            curr = find(curr)
            
    # 板 1 から N までの最終的な色番号をスペース区切りで出力します。
    # 大量のデータを出力するため sys.stdout.write を使用します。
    sys.stdout.write(" ".join(map(str, ans[1:])) + "\n")

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-thinking.