概要

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

考察

素朴なアプローチの問題点

最も単純な方法は、各操作ごとに板 \(L_i\) から \(R_i\) まで1枚ずつ色を塗ることです。しかし、1回の操作で最大 \(N = 5 \times 10^5\) 枚を塗る可能性があり、操作が \(M = 2 \times 10^5\) 回あるため、最悪 \(O(NM) = 10^{11}\) 程度の計算量になり、TLE（時間超過）になります。

重要な気づき：「最後に塗った色」だけが意味を持つ

各板の最終的な色は、その板を最後に塗った操作の色で決まります。つまり、同じ板を何度も塗っても、最後の操作以外は無駄です。

この性質を利用すると、操作を逆順（後ろから）に処理できます。逆順に見て、ある操作 \([L_i, R_i, C_i]\) を処理するとき、まだ色が確定していない（＝まだどの操作にも割り当てられていない）板だけに色 \(C_i\) を割り当てれば良いのです。一度色が確定した板は、それ以降（逆順でいうそれ以前の操作）では無視できます。

問題：未塗装の板を高速に見つけるには？

逆順処理で区間 \([L_i, R_i]\) 内の未塗装の板を見つけたいですが、単純に1枚ずつ調べると結局 \(O(NM)\) になりかねません。ここで Union-Find（素集合データ構造）の経路圧縮テクニック を使います。

アルゴリズム

「次の未塗装位置」を管理する Union-Find

配列 parent[i] を用意し、「位置 \(i\) 以上で最も近い未塗装の板の番号」を管理します。

• 初期状態: parent[i] = i（すべて未塗装なので、自分自身が未塗装）
• 板 \(i\) を塗ったとき: parent[i] = i + 1 とする（位置 \(i\) はもう塗装済みなので、次の未塗装位置は \(i+1\) 以降）
• find(x): 経路圧縮付きで parent を辿り、位置 \(x\) 以上の最初の未塗装位置を返す

処理の流れ

1. 操作を逆順に処理する（\(i = M, M-1, \ldots, 1\)）
2. 操作 \([L_i, R_i, C_i]\) に対して、pos = find(L_i) で区間内の最初の未塗装位置を取得
3. pos <= R_i の間、板 pos に色 \(C_i\) を割り当て、parent[pos] = pos + 1 として次へ進む
4. すべての操作を処理した後、色が割り当てられなかった板は初期値 \(0\) のまま

具体例

\(N = 5, M = 2\)、操作1: \([1, 4, 3]\)、操作2: \([2, 5, 7]\) の場合：

• 逆順で操作2を処理: 板2,3,4,5 に色7を割り当て → boards = [0, 7, 7, 7, 7]
• 逆順で操作1を処理: \([1,4]\) の未塗装板を探す → 板1のみ未塗装 → 板1に色3を割り当て
• 最終結果: 3 7 7 7 7

計算量

• 時間計算量: \(O(N + M \cdot \alpha(N))\)（\(\alpha\) はアッカーマン関数の逆関数で、実質定数。各板は高々1回だけ塗られるため、全操作を通じた塗装回数の合計は \(O(N)\)）
• 空間計算量: \(O(N + M)\)

実装のポイント

• parent 配列のサイズは \(N+2\) にする。parent[N+1] が番兵として機能し、find が \(N+1\) を返した時点で区間外と判定できる

• Python では再帰による find はスタックオーバーフローの危険があるため、ループ＋経路圧縮（path halving） で実装している（parent[x] = parent[parent[x]]）

• 入力は sys.stdin.buffer.read() で一括読み込みし、高速化している

  ソースコード

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

---

この解説は claude4.6opus-thinking によって生成されました。