概要

塗り替え操作をそのまま順にシミュレーションすると遅すぎるため、操作を逆順に見て「まだ色が確定していない板だけを一度だけ塗る」ことで高速に解く問題です。
未確定の次の位置を高速に飛ばすために、Union-Find（次未処理位置管理）を使います。

考察

重要な観察は次の2つです。

1. 板の最終色は「最後にその板を塗った操作」で決まる
   
2. ならば操作を後ろから見ると、ある板に最初に出会った色がそのまま最終色になる

素朴に各操作で区間 \([L_i, R_i]\) を全部塗ると、最悪で
\(M \times N \approx 2\times10^5 \times 5\times10^5\) となり到底間に合いません。

逆順で考えると、「すでに色が確定した板」はもう触る必要がありません。
そこで「未確定の板のうち、位置 \(x\) 以上で最初のもの」をすぐ求められれば、確定済み区間をまとめて飛ばせます。

この“次の未確定位置へジャンプ”を実現するのが今回の Union-Find 的な配列 parent です。
parent[x] は「\(x\) が確定済みなら次に見るべき候補」を指すようにし、find(x) で代表（未確定の実位置）を取得します。

アルゴリズム

1. ans[1..N] = 0（未塗装）で初期化。
2. parent[i] = i を用意し、番兵 N+1 も作る。
3. 操作列を逆順に処理する：
   • 操作 \((l, r, c)\) に対して x = find(l)
   • x <= r の間：
     • ans[x] = c（この板の最終色が確定）
     • parent[x] = find(x+1) として、次回から x を飛ばせるようにする
     • x = parent[x] で次の未確定板へ進む
4. 最後に ans[1..N] を出力。

イメージ

例えば逆順で区間 \([2,5]\) を処理中に、3,4 が既に確定済みなら、find(2) の次は一気に 5 や 6 へ飛べます。
各板は確定時に1回だけ処理されるので高速です。

計算量

• 時間計算量: \(O((N+M)\alpha(N))\)（ほぼ線形）
• 空間計算量: \(O(N+M)\)（ops, parent, ans）

実装のポイント

• parent は N+2 長で作り、N+1 を番兵にする（範囲外アクセス防止）。

• find は経路圧縮を入れると高速化できる（コードでは while + 圧縮）。

• 逆順処理が本質。順方向で同じことをしようとすると難しくなります。

• M=0 のときもそのまま ans は全部 0 で正しく出力されます。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    ops = [tuple(map(int, input().split())) for _ in range(M)]

    parent = list(range(N + 2))  # 1..N, sentinel N+1
    ans = [0] * (N + 1)

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

    for l, r, c in reversed(ops):
        x = find(l)
        while x <= r:
            ans[x] = c
            parent[x] = find(x + 1)
            x = parent[x]

    print(*ans[1:])

if __name__ == "__main__":
    main()

この解説は gpt-5.3-codex によって生成されました。