Codeforces #353D (Div. 2) STL+数据结构性质

题目链接：原题

题目大意是指一堆不同数插入到一个 排序二叉树（二叉搜索树）中去，让你去求一下每一个的父亲是谁；

这题显然耿直的去建树是不行的，因为会有退化成链的情况嘛，所以考虑一下插入时候的性质就可以了。

插入时无非是插入到恰比它小的右节点，或恰比它大的左节点。。

这时我们就可以愉快的用set来维护了（cf不愧是练习stl的好地方）。

PS。测评机跑的飞快。。。

代码：

#include <bits/stdc++.h>

using namespace std;

set<int> S;
map<int,int> L,R,F;

int main(){
    int n,x;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&x);
        if(i==0){
            S.insert(x);
            continue;
        }
        auto it=S.lower_bound(x);
        if(it==S.begin()){
            L[*it]=1;
            F[x]=*it;
            S.insert(x);
        }
        else if(it==S.end()){
            it--;
            R[*it]=1;
            F[x]=*it;
            S.insert(x);
        }
        else{
            it--;
            if(R.count(*it)==0){
                R[*it]=1;
                F[x]=*it;
                S.insert(x);
            }
            else{
                it++;
                L[*it]=1;
                F[x]=*it;
                S.insert(x);
            }
        }
        printf("%d ",F[x]);
    }
    return 0;
}