AIによる解説には計算量が \(O((N+M)\alpha(N))\) と書かれていますが誤りです。AIの実装はいずれも Union By Size/Union By Rank なしで Path Halving/Path Compression をしているため、計算量は find 1 回あたりならし \(O(\log N)\) としか示せません。全体で \(O((N+M)\log N)\) となります。

解法1：DSU

色を塗る操作を逆から処理することにします。一度色が塗られたマスの色が上書きされることはないので、「まだ色を塗っていない次のマス」を高速に見つけることができれば、全体を高速に処理できます。

DSU を用いて、各マスに対応する頂点が「まだ色を塗っていない次のマス」を指す有向木を管理することでならし \(O(\log N)\) 時間でそのようなマスを見つけることができます。

計算量は \(O((N+M)\log N)\) になります。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

struct dsu {
    dsu(int n) : parent(n, -1) {}

    void merge(int a, int b) {
        int x = leader(a), y = leader(b);
        if (x == y) return;
        if(x < y) swap(x, y);
        parent[y] = x;
    }

    int leader(int a) {
        if (parent[a] < 0) return a;
        return parent[a] = leader(parent[a]);
    }

    vector<int> parent;
};

int main(){
  int n, m;
  cin >> n >> m;
  vector<array<int,3>>query(m);
  for(int i=0; i<m; i++){
    cin >> query[i][0] >> query[i][1] >> query[i][2];
    query[i][0]--;
  }
  reverse(query.begin(), query.end());

  dsu d(n+1);
  vector<int>ans(n);
  for(auto[l, r, c]: query){
    while(l < r){
      if(ans[l] == 0){
        ans[l] = c;
        d.merge(l, l+1);        
      }
      l = d.leader(l);
    }
  }

  for(int i=0; i<n; i++){
    cout << ans[i] << endl;
  }
}

Pythonの自然な実装では通せませんでした（2ケース TLE）

解法2：区間を set で管理するテク

色を塗る操作を逆から処理することにします。一度色が塗られたマスの色が上書きされることはないので、「まだ色を塗っていない次のマス」を高速に見つけることができれば、全体を高速に処理できます。

すでに色が塗られているマスの極大な区間を set で管理し、二分探索することで「まだ色を塗っていない次のマス」を高速に見つけることができます。

計算量は \(O((N+M)\log N)\) になります。（python の SortedSet はそれより計算量が悪いですが、この問題ではACすることができます）

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n, m;
  cin >> n >> m;
  vector<array<int,3>>query(m);
  for(int i=0; i<m; i++){
    cin >> query[i][0] >> query[i][1] >> query[i][2];
    query[i][0]--;
  }
  reverse(query.begin(), query.end());

  set<pair<int,int>>s;
  vector<int>ans(n);
  for(auto[l, r, c]: query){
    int crr = l;
    while(crr < r){
      if(ans[crr] == 0){
        ans[crr] = c;
        crr++;
      }else{
        auto it = s.lower_bound({crr,-1});
        if(it != s.end() && it -> first == crr){
          crr = it -> second;
        }else{
          it--;
          crr = it -> second;
        }
      }
    }
    // [l,r) と重なる区間をマージしながら削除
    int right = r;
    int left = l;
    auto it = s.upper_bound({l, n+1});
    if(it != s.begin())it--;
    while(it != s.end() && it -> first <= right){
      if(it -> second >= left){
        left = min(left, it -> first);
        right = max(right, it -> second);
        it = s.erase(it);
      }else{
        it++;
      }
    }
    s.insert({left, right});
  }

  for(int i=0; i<n; i++){
    cout << ans[i] << endl;
  }
}

実装例 (Python)

from sortedcontainers import SortedSet

N, M = map(int, input().split())
query = []
for _ in range(M):
    L, R, C = map(int, input().split())
    query.append((L - 1, R, C))
query.reverse()

ans = [0] * N
s = SortedSet()

for L, R, C in query:
    crr = L
    while crr < R:
        if ans[crr] == 0:
            ans[crr] = C
            crr += 1
        else:
            idx = s.bisect_left((crr, -1))
            if idx < len(s) and s[idx][0] == crr:
                crr = s[idx][1]
            else:
                idx -= 1
                crr = s[idx][1]

    # [L,R) と重なる区間をマージしながら削除
    left, right = L, R
    idx = s.bisect_right((L, N + 1))
    if idx > 0:
        idx -= 1
    while idx < len(s):
        L, R = s[idx]
        if L > right:
            break
        if R >= left:
            left = min(left, L)
            right = max(right, R)
            s.pop(idx)
        else:
            idx += 1
    s.add((left, right))

print(*ans)

解法3：遅延セグメント木

区間代入操作が可能な遅延セグメント木を用いることで、問題文の指示通りクエリを高速に処理することができます。計算量は \(O((N+M)\log N)\) になります。

実装例 (C++)

#include<bits/stdc++.h>
#include<atcoder/lazysegtree>
using namespace std;

using X = int;
using F = pair<int,int>;
X xx(X x, X y){return 0;}
X xid(){return 0;}
X fx(F f, X x){return f.first * x + f.second;}
F ff(F f, F g){return {f.first * g.first, f.first * g.second + f.second};}
F fid(){return {1, 0};}

int main(){
  int n,m;
  cin >> n >> m;
  atcoder::lazy_segtree<X, xx, xid, F, fx, ff, fid>seg(n);
  for(int i=0; i<m; i++){
    int l, r, c;
    cin >> l >> r >> c;
    seg.apply(l-1, r, {0,c});
  }
  for(int i=0; i<n; i++)
    cout << seg.get(i) << ' ';
  }
}

実装例 (Python)

from atcoder.lazysegtree import LazySegTree

def xx(x, y): return 0
xid = 0
def fx(f, x): return f[0] * x + f[1]
def ff(f, g): return (f[0] * g[0], f[0] * g[1] + f[1])
fid = (1, 0)


N, M = map(int, input().split())
seg = LazySegTree(xx, xid, fx, ff, fid, N)
for _ in range(M):
  L, R, C = map(int,input().split())
  seg.apply(L-1, R, (0, C))

ans = [seg.get(i) for i in range(N)]
print(*ans)