CF #207 A: Knight Tournament (356A) - かわらにかわらは割れない

セグ木で解けると聞いて解こうとしたけど、無理だったのでセグ木を使わず解いた。

問題概要

$1$ 〜 $n$ までの番号が付いた $n$ 人の王様が、勝ち残り形式で勝負をします。勝負は $m$ 回行われます。勝負は順次行われていき、 $i$ 番目の勝負の情報として "戦った王様の中で一番小さい番号が $l_i$ 、大きい番号が $r_i$ 番目であり、王様 $x_i$ が勝ち抜いた" が与えられます。各王様がどの王様に倒されたかを出力してください。優勝した王様に関しては $0$ を出力してください。

解法

セグ木を使うと聞いていたのでセグ木で解こうとしたが、更新時、クエリ時の動きが分からなくて断念した。よくよく考えると、勝負は順番に行われていくので、「 $l_i\le k\le r_i$ なる王様 $k$ が戦う勝負に関して、まだ誰に倒されたかが分かっていないときは王様 $k$ が倒された相手として $x_i$ を記録しておく」ことで誰に倒されたかが分かります。

実際に解くときはsetでまだ誰に倒されたか分かっていない王様を管理しておき、誰に倒されたか分かった時点でsetから除いていく（erase関数を使う）ことでうまく誰に倒されたかが分かります。 $i$ 番目の勝負の勝者である $x_i$ に関してはまだ誰に倒されたかが分からないので、その王様に関してだけスキップすることに注意です。計算量は $O(nlogn)$ です（間違っていたらすみません）

提出：
https://codeforces.com/contest/356/submission/60293084

計算量が間違っていたり、セグ木での解き方が分かる方は教えてください。