Codeforces #353 Div2 D. Tree Construction

これも無駄に手間取った。
http://codeforces.com/contest/675/problem/D

問題

全要素が異なる数列Aが与えられる。
A[0]を根とし、A[i]を順に追加して作れる二分ヒープを考える。(途中回転等は行わない)

得られる二分ヒープに対し、A[i]の親頂点の値を答えよ。

解法

既に二分ヒープに加えられた値xに対し、根からの深さをD(x)とする。
これから値yを加えることを考えよう。
既に二分ヒープにあるy未満の最大値をa,yより大きい最小値をbとする。

D(a)とD(b)は必ず異なる。
(仮にD(a)==D(b)となるなら、aとbの間により深さの低い頂点がなければならないが、a,bの選び方より間に他の値が入ることはないのであり得ない)

D(a)＞D(b)ならyはaの右子頂点に、D(a)＜D(b)ならyはnの左子頂点に加えていけば良い。

int N;
int A[101010],H[101010],P[101010];
map<int,int> M;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		if(i) {
			auto it=M.lower_bound(A[i]);
			if(it==M.end()) {
				it--;
			}
			else if(it!=M.begin()) {
				auto it2=it;
				it--;
				if(it->second<it2->second) swap(it,it2);
			}
			H[i]=it->second+1;
			P[i]=it->first;
		}
		M[A[i]]=H[i];
	}
	
	for(i=1;i<N;i++) _P("%d%s",P[i],(i==N-1)?"\n":" ");
	
	
}

まとめ

色々考えたのち結局こんな単純でいいことに気が付いた。
当初SegTreeとか使ってえらく複雑なコードでWAを連発してしまった。