TIOJ 1332 - 名義老爸

Link: http://tioj.ck.tp.edu.tw/problems/1332

用map(也可用set包pair)隨便亂寫AC，插入的時候用map找比它大和比它小的兩數分別是誰，誰比較晚插入誰就是它的爸爸。
複雜度O(nlgn)，據說正解是用笛卡爾樹O(n)，參考:
http://ckhs1328.pixnet.net/blog/post/40525136-tioj-1332-%E5%90%8D%E7%BE%A9%E8%80%81%E7%88%B8
http://cbdcoding.blogspot.tw/2015/03/tioj-1332.html

AC code

#include<bits/stdc++.h>
using namespace std;
int ans[1000010];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n;
    cin>>n;
    map<int,int> st;
    st.insert({0,-1});
    st.insert({n+1,-2});
    for(int i=0;i<n;i++)
    {
        int t;
        cin>>t;
        map<int,int>::iterator it1=st.lower_bound(t), it2=it1;
        it1--;
        if(it1->second > it2->second)
            ans[t]=it1->first;
        else
            ans[t]=it2->first;
        st.insert({t,i});
    }
    for(int i=1;i<=n;i++)
        cout<<ans[i]<<'\n';
}