読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Codeforces Round #353 (Div. 2) D. Tree Construction

http://codeforces.com/contest/675/problem/D

問題

二分探索木の動作をシミュレーションせよ。

i 回目の操作で挿入された値の親の値を出力すればよい。挿入する値は distinct であることが保証されている。

  • 2≦n≦105
  • 1≦a[i]≦109

解法

下図のような二分木に 5 を追加したいとする。5 は 3 と 6 の間にある数なので、3 と 6 のどちらかの子供になるはずである。

f:id:pekempey:20160517062259p:plain

すでに挿入されている値を std::set で保持しておけば lower_bound で親の候補が得られる。

どっちが正しい親なのか判定するにはノードの深さを見ればいい。3 と 6 では 3 の方が深いので 3 が正しい親である。


set::iterator は +1 とか -1 ができないのだけど、next, prev 関数を使えば次(前)の iterator が取れる(豆知識)。

Codeforces Round #353 (Div. 2) D. Tree Constructio ...

似た問題を解いたことがあったので即殺でした。