题目链接：http://codeforces.com/problemset/problem/675/D
给你一个如题的二叉树，让你求出每个节点的父节点是多少。
用set来存储每个数，遍历到a[i]的时候查找比a[i]大的数的位置，然后插入，而父亲就是刚好比a[i]小的数或刚好大的数。
然后讨论是哪一个数。
比如给你3 1 2 ，如图
1的父亲是3 ，2的父亲是1。
那我其实只要找左边或右边出现最晚的数就行了，用pair的first表示a[i]，second表示出现的顺序i。
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef pair <int , int> P; 4 int a[int(1e5 + 5)] , ans[int(1e5 + 5)]; 5 set <P> v; 6 int main() 7 { 8 int n; 9 scanf("%d" , &n); 10 for(int i = 0 ; i < n ; ++i) { 11 if(i == 0) { 12 scanf("%d" , a + i); 13 v.insert(P(a[i] , i)); 14 continue; 15 } 16 scanf("%d" , a + i); 17 auto it = v.upper_bound(P(a[i] , 0)); 18 if(it == v.begin()) { 19 ans[i] = it->first; 20 } 21 else if(it == v.end()) { 22 ans[i] = (--it)->first; 23 } 24 else { 25 if(it->second > (--it)->second) 26 ans[i] = (++it)->first; 27 else 28 ans[i] = it->first; 29 } 30 v.insert(P(a[i] , i)); 31 } 32 for(int i = 1 ; i < n - 1 ; ++i) 33 printf("%d " , ans[i]); 34 printf("%d " , ans[n - 1]); 35 }