ABC217 D Cutting Woods
次のようなアルゴリズムで解くことができる.
setを用意し,
$ 0, L
を追加する.
$ c_i = 1
のとき, setに
$ x_i
を追加する.
$ c_i = 2
のとき,
$ x_i
がset内の要素のうちどこに入るか二分探索で求め, 入る場所の(右の要素) - (左の要素)を出力する.
このアルゴリズムの計算量は
$ O(N \log N)
である.
実装例:
https://atcoder.jp/contests/abc217/submissions/25565481