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

D. Tree Construction

链接：

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

题意：

给你平衡树的节点，每个节点都依次插进去的，问你每个节点插进去之后，他的父亲是谁

题解：

没必要真的写个平衡树，直接用stl模拟就好了……

代码：

 1 #include<iostream>
 2 #include<set>
 3 #include<map>
 4 using namespace std;
 5 
 6 typedef pair<int, int> P;
 7 set<int> s;
 8 map<int, P> m;
 9 
10 int main()
11 {
12     int n, x;
13     cin >> n >> x;
14     s.insert(x);
15     n--;
16     while (n--) {
17         cin >> x;
18         auto it = s.lower_bound(x);
19         if (it == s.end()) m[*--it].second = x;
20         else if (m[*it].first == 0) m[*it].first = x;
21         else m[*--it].second = x;
22         cout << *it << ' ';
23         s.insert(x);
24     }
25     cout << endl;
26     return 0;
27 }