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

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

問題

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

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

• 2≦n≦10⁵
• 1≦a[i]≦10⁹

解法

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

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

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

---

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

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

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