Codeforces #332 Div2 C. Day at the Beach

また手抜き実装してDミスした。
http://codeforces.com/contest/599/problem/C

問題

N要素の数列がある。
これらの数列を幾つかの連続した部分列に分割することを考える。

分割した部分列をそれぞれソートしてまた元通り連結したとき、全体の数列が昇順になるようにしたい。
数列を最大何個の部分列に分割できるか。

解法

各数列の要素より後ろに、より小さな要素がある場合、その２要素は順序を入れ替えないので条件を満たさないのでそれらは同じ部分列に含めなければならない。
よって各要素にあるより小さな要素の位置を順次求めていこう。

各要素に対し、含めなければいけない後ろの要素を求めたら、同じ部分列に含まれなければいけない区間が求まるのでそれを数え上げるだけ。
自分は「各要素に対し、含めなければいけない後ろの要素」をソートを使って求めたが、O(N)でも解けるようだ。

int N;
int H[101010];
int R[101010];
map<int,vector<int> > M;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>H[i];
		M[H[i]].push_back(i);
	}
	
	int right=-1;
	FORR(r,M) {
		int nr=-1;
		FORR(r2,r.second) nr = max(nr,r2), R[r2]=right;
		right = max(nr,right);
	}
	
	x=0,r=-1;
	FOR(i,N) {
		if(r<i) x++;
		r=max(r,R[i]);
	}
	cout<<x<<endl;
}

まとめ

本番無駄にSegTreeとか使っちゃった。