TopCoder SRM 750 Div1 Medium SimulateBST

知ってると簡単。
https://community.topcoder.com/stat?c=problem_statement&pm=15302

問題

ある数列を、順に二分木に追加していく。
各要素の挿入される位置に対応する頂点の深さを求めよ。

解法

数値Xを追加するとき、二分木中でX未満の最大値をL、Xより大きい最小値をRとする。
また、それぞれの対応する頂点の深さをD(X),D(L),D(R)とする。
その時、D(X)=max(D(L),D(R))+1となるので、それを愚直に計算しよう。

端に追加される場合の処理が面倒だが、先にD(inf)=D(-inf)=-1としておくと、端に追加されるケースがないのでそれを無視できる。

int D[505050];
ll mo=1000000007;

class SimulateBST {
	public:
	int checksum(int n, vector <int> S, int a, int m) {
		int SZ=S.size();
		int i;
		map<int,int> mp;
		ll ret=0;
		ll p=1;
		mp[-1]=mp[1<<30]=-1;
		FOR(i,n) {
			if(i>=SZ) S.push_back((a*1LL*S[i-SZ]+D[i-1]+1)%m);
			
			if(mp.count(S[i])==0) {
				auto it=mp.lower_bound(S[i]);
				int R=it->second;
				it--;
				int L=it->second;
				mp[S[i]]=max(L,R)+1;
			}
			D[i]=mp[S[i]];
			ret=(ret+D[i]*p)%mo;
			p=p*100000%mo;
		}
		
		return ret;
		
	}
}

まとめ

この特性、以前どっかで見たんだけどなんだったかな…。