ferinの競プロ帳

競プロについてのメモ

codeforces #207 div1 A. Knight Tournament

問題ページ
Problem - A - Codeforces

解法

[l_i, x_i)、(x_i、r_i]の区間でまだ誰にも負けていない兵士がいればその兵士はx_iに負けたとして更新していけばよさそう。すでに負けた、負けていないを管理するのが大変そうだったのでクエリを逆に読んで、管理しなくてもいいようにする。
遅延セグ木を使えば各クエリに対して[l_i, x_i) (x_i, r_i]の区間にx_iを更新するのをO(logN)でできる。結果を出力する前に各頂点に遅延更新をしないと正しい答えにならないので注意。