题目链接：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。
#include <bits/stdc++.h>
using namespace std;
typedef pair <int , int> P;
int a[int(1e5 + )] , ans[int(1e5 + )];
set <P> v;
int main()
{
int n;
scanf("%d" , &n);
for(int i = ; i < n ; ++i) {
if(i == ) {
scanf("%d" , a + i);
v.insert(P(a[i] , i));
continue;
}
scanf("%d" , a + i);
auto it = v.upper_bound(P(a[i] , ));
if(it == v.begin()) {
ans[i] = it->first;
}
else if(it == v.end()) {
ans[i] = (--it)->first;
}
else {
if(it->second > (--it)->second)
ans[i] = (++it)->first;
else
ans[i] = it->first;
}
v.insert(P(a[i] , i));
}
for(int i = ; i < n - ; ++i)
printf("%d " , ans[i]);
printf("%d\n" , ans[n - ]);
}