[TIOJ] 1332. 名義老爸

題目連結:http://tioj.infor.org/problems/1332

---

可以發現對於每個點的爸爸必定是在他出現前出現過的，且必定是比他大的最小值或比他小的最大值中較後面插入的數，不過詳細的證明我不太會證...如果有大大願意教我一下我洗耳恭聽。
因此就用個map存每個數，因為要快速找到比他大的最小值跟比他小的最大值，所以不妨把值當作key，插入順序當作value，就得到了一個$O(N log N)$的做法了。
不過本題其實還有更快的做法，複雜度可變成$O(N)$，那就是對於這個數列用奇怪的方式(?建出一顆笛卡爾樹，再轉回原數列即可知道答案，雖然你還是會構造出整棵樹，但因為笛卡爾樹有線性的建法，所以複雜度還是$O(N)$
詳細可參考:這篇(我覺得比較好理解在幹嘛) 跟 這篇 有講怎麼線性構造出笛卡爾樹

#include <bits/stdc++.h>
using namespace std;
#define N 1000000

int ans[N+5];
map<int,int> mp;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n;cin>>n;
	for(int i=1;i<=n;++i){
		int x;cin>>x;
		int l=-1,r=-1,ll,rr;
		auto it = mp.insert({x,i}).first;
		++it;
		if(it!=mp.end()){
			l=it->second;
			ll=it->first;
		}
		--it;
		if(it!=mp.begin()){
			--it;
			r=it->second;
			rr=it->first;
		}
		if(l==-1&&r==-1) ans[x]=0;
		else if(l==-1) ans[x]=rr;
		else if(r==-1) ans[x]=ll;
		else if(r>l) ans[x]=rr;
		else ans[x]=ll;
	}
	for(int i=1;i<=n;++i) cout<<ans[i]<<'\n';
	return 0;
}