概要

\(N\) 枚の板に対して \(M\) 回の区間塗り替えを行い、最終的な各板の色を求める問題です。塗り替えは「上書き」であるため、各板において最後に塗られた色が最終的な色となります。

考察

素朴なアプローチ

各クエリ \((L_i, R_i, C_i)\) に対して、実際に \(L_i\) から \(R_i\) までの配列要素を書き換える方法が考えられます。しかし、最悪の場合（全てのクエリが全範囲を塗る場合など）、計算量は \(O(N \times M)\) となります。本問題の制約は \(N \le 5 \times 10^5, M \le 2 \times 10^5\) であるため、最大で \(10^{11}\) 回程度の操作が必要になり、実行時間制限に間に合いません。

逆順に考える

この問題の急所は、「ある板が一度塗られたら、それより前の操作で何色に塗られようとも最終的な色には影響しない」という点です。

そこで、塗り替えのクエリを後ろ（\(M\) 回目）から順に処理することを考えます。 1. \(M\) 回目の操作で範囲 \([L_M, R_M]\) を色 \(C_M\) で塗る。 2. 次に、まだ塗られていない板のうち、\(M-1\) 回目の操作の範囲 \([L_{M-1}, R_{M-1}]\) に含まれるものを色 \(C_{M-1}\) で塗る。 3. これを \(1\) 回目の操作まで繰り返す。

この方法なら、各板は「一度色が塗られたら、それ以降の探索ではスキップすればよい」ことになります。

効率的なスキップの方法

「まだ塗られていない板」を効率よく探すために、素集合データ構造（Union-Find / DSU）の考え方を応用します。 parent[i] という配列を用意し、「インデックス i 以降で、まだ塗られていない可能性がある最小のインデックス」を保持するようにします。 ある板 i を塗った直後に、その板を「次のインデックス（i + 1）」に結合することで、次に同じ場所を訪れた際に find 関数を使って一気に未塗装の場所までジャンプできるようになります。

アルゴリズム

1. 逆順処理: クエリを \(i = M, M-1, \dots, 1\) の順に処理します。
2. 未塗装部分の探索:
   • 現在のクエリの左端 \(L_i\) から出発し、curr = find(L_i) によって「\(L_i\) 以降で最初の未塗装の板」を見つけます。
   • その curr が右端 \(R_i\) 以下である限り、以下の操作を繰り返します。
     1. 板 curr の色を \(C_i\) に決定する。
     2. 板 curr は塗装済みになったので、parent[curr] = find(curr + 1) として次のインデックスへリンクさせる。
     3. curr = find(curr) で次の未塗装の板へジャンプする。
3. 経路圧縮: find 関数の中で親を書き換える（経路圧縮）ことで、ジャンプの計算量をほぼ定数時間に抑えます。

計算量

• 時間計算量: \(O((N + M) \alpha(N))\)
  • 各板が「未塗装」から「塗装済み」になるのは一度きりです。Union-Find の経路圧縮を利用することで、各クエリでのジャンプ操作はならし計算量で非常に高速（アッカーマン関数の逆関数 \(\alpha(N)\)）になります。
• 空間計算量: \(O(N + M)\)
  • 板の色を保持する配列、DSUの配列、およびクエリの保存に \(N\) や \(M\) に比例したメモリを使用します。

実装のポイント

• 再帰制限: Python で Union-Find を実装する場合、再帰による find は sys.setrecursionlimit を設定しないと最大 \(N\) の深さでエラーになります。今回のコードのように、ループ（while 文）による反復実装にすることで、再帰制限を回避しつつ高速に動作させることができます。

• 高速な入出力: \(N, M\) が大きいため、input() ではなく sys.stdin.read().split() を使用し、出力も sys.stdout.write を用いることで入出力のボトルネックを解消しています。

  ソースコード

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()

この解説は gemini-3-flash-thinking によって生成されました。