概要

塗り替えを前からそのままシミュレーションすると遅すぎるので、後ろから逆順に処理するのがポイントです。
さらに、すでに最終色が確定した板を高速に飛ばすために、Union-Find のような「次に未確定の位置を探す」データ構造を使います。

考察

この問題では、区間 \([L_i, R_i]\) を色 \(C_i\) で何度も上書きします。
求めたいのは「最後に残る色」なので、重要なのは 最後にその板を塗った操作 です。

素朴な方法

各操作ごとに、区間内の板を全部塗り直すとします。

• 1 回の操作で最大 \(N\) 枚塗る
• 操作回数は最大 \(M\)

したがって最悪計算量は \(O(NM)\) になります。
制約では

• \(N \le 5 \times 10^5\)
• \(M \le 2 \times 10^5\)

なので、最悪で \(10^{11}\) 回級の更新になり、当然間に合いません。

---

重要な気づき：後ろから見れば「最初に塗った色」が答え

たとえば操作列が

1. \([2,5]\) を色 3
2. \([4,7]\) を色 8
3. \([1,3]\) を色 2

だったとします。

前から見ると何度も上書きされて複雑ですが、後ろから見ると事情が変わります。

• 操作 3 を見ると、板 \(1,2,3\) の最終色はまだ未確定なので色 2 に決まる
• 次に操作 2 を見ると、板 \(4,5,6,7\) のうち未確定なものだけ色 8 に決まる
• 最後に操作 1 を見ても、板 \(2,3,4,5\) はもう確定済みなので無視できる

つまり、逆順に処理すると、各板は最初に出会った操作で最終色が確定するのです。

---

それでも区間を毎回なめると遅い

逆順にしても、各操作で \(L_i\) から \(R_i\) を順に見て

• まだ未確定なら塗る
• 確定済みなら飛ばす

としていると、結局たくさんの位置を何度も見る可能性があり、まだ遅いです。

---

どう高速化するか

そこで、「次の未確定の板」をすぐ見つける仕組みを用意します。

parent[x] を
「位置 \(x\) 以上で、まだ色が確定していない最左の位置」
をたどるために使います。

板 \(x\) の色を確定させたら、もう今後そこを見る必要はありません。
そこで

• 板 \(x\) を確定させた後
• parent[x] = find(x + 1)

とします。

これにより、「\(x\) はもう処理済みなので、次は \(x+1\) 以降を見てね」という情報を持たせられます。

この方法なら、一度確定した板は次回以降すべてまとめて飛ばせます。
各板は高々 1 回しか確定されないので、全体で高速になります。

アルゴリズム

使う考え方は、逆順処理 + Union-Find（Disjoint Set Union）風のスキップです。

データ構造

• ans[i]: 板 \(i\) の最終色
• parent[i]: 「\(i\) 以上でまだ未確定の最左位置」を探すための配列
• find(x): 経路圧縮付きで代表を求める関数

初期状態では、どの板も未確定なので

• parent[i] = i

としておきます。
また、番兵として N+1 も用意しておくと、区間の右端を超えた判定がしやすいです。

---

処理手順

1. すべての操作を配列に保存する
2. 操作を後ろから順に見る
3. 操作 \((L_i, R_i, C_i)\) に対して
   • p = find(L_i) で、区間内の未確定な最初の位置を探す
   • p <= R_i の間:
     • ans[p] = C_i として色を確定
     • その位置はもう不要なので、parent[p] = find(p + 1) にする
     • 次の未確定位置へ進む
4. 最後に ans[1] から ans[N] を出力

---

具体例

\(N=8\)、操作が以下だとします。

1. \([2,6] \leftarrow 5\)
2. \([4,8] \leftarrow 7\)
3. \([3,5] \leftarrow 2\)

逆順に処理します。

操作 3: \([3,5] \leftarrow 2\)

未確定の 3,4,5 を色 2 にする。

操作 2: \([4,8] \leftarrow 7\)

4,5 はもう確定済みなので飛ばす。
6,7,8 を色 7 にする。

操作 1: \([2,6] \leftarrow 5\)

3,4,5,6 は確定済みなので飛ばす。
2 だけ色 5 にする。

最終結果は

• 1: 0
• 2: 5
• 3,4,5: 2
• 6,7,8: 7

となります。

このように、確定済みの場所を Union-Find で一気に飛ばすのが核心です。

計算量

• 時間計算量: \(O((N + M)\alpha(N))\)
• 空間計算量: \(O(N + M)\)

ここで \(\alpha(N)\) はアッカーマン関数の逆関数で、実用上ほぼ定数です。
感覚的には、各板は 1 回だけ確定されるので非常に高速です。

実装のポイント

• 操作は前からではなく後ろから処理する
• find(x) で「次の未確定位置」を求める
• 板 p を確定したら、parent[p] = find(p + 1) として以後飛ばせるようにする
• N+1 を番兵として用意しておくと、p <= R の判定が簡単になる
• 提示コードでは array('I') を使っており、大きな入力に対して Python の通常リストよりメモリ効率がよい

この実装の本質は、Union-Find を「連結判定」に使うのではなく、
未処理の次の位置を高速に探すためのデータ構造として使っている点です。

ソースコード

import sys
from array import array

input = sys.stdin.buffer.readline

N, M = map(int, input().split())

L = array('I')
R = array('I')
C = array('I')

for _ in range(M):
    l, r, c = map(int, input().split())
    L.append(l)
    R.append(r)
    C.append(c)

parent = array('I', range(N + 2))
ans = array('I', [0]) * (N + 1)

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

for i in range(M - 1, -1, -1):
    l = L[i]
    r = R[i]
    c = C[i]
    p = find(l)
    while p <= r:
        ans[p] = c
        nxt = find(p + 1)
        parent[p] = nxt
        p = nxt

sys.stdout.write(' '.join(map(str, ans[1:])))

---

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