Codeforces #777 : Div2 F. Madoka and Laziness

コードは短い。
https://codeforces.com/contest/1647/problem/F

問題

整数列が丘であるとは、途中まで単調増加でその後単調減少していることとする。
整数列Aが与えられる。Aの各要素は重複しない。

このAを2つの丘となる部分列に分割できる場合、両丘の最大値のペアは何通りか。

解法

1個の丘の最大値は、Aの最大値で一意に決まる。
そこで問題はもう一つの最大値をどこに取るかである。

2個目の丘の最大値をA[i]が、A全体の最大値がA[j]としたとき、i＜jとする。

• i以前のindexは、どちらの丘においても単調増加列の一部なす
• j以降のindexは、どちらの丘においても単調減少列の一部なす
• i以降j以前のindexは、1個目の丘に組み込まれたら単調増加列、2個目の丘なら単調減少列の一部なす

L[x] := x番までを2つの単調増加列に分割したとき、A[x]が入らない方の数列の最大値
R[x] := x番以降を2つの単調減少列に分割したとき、A[x]が入らない方の数列の最大値
を2つあらかじめ計算しておくと、iを総当たりしたときに、iを2つ目の丘の最大値とできるかどうか判定できる。

int N;
int A[505050];

int L[505050],R[505050],M[505050][2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i+1];
	int ret=0;
	
	FOR(r,2) {
		reverse(A+1,A+N+1);
		int ma=1;
		FOR(i,N) if(A[i+1]>A[ma]) ma=i+1;
		
		for(i=1;i<=ma;i++) {
			L[i]=1<<30;
			if(A[i]>L[i-1]) L[i]=min(L[i],A[i-1]);
			if(A[i]>A[i-1]) L[i]=min(L[i],L[i-1]);
		}
		
		for(i=N;i>=ma;i--) {
			R[i]=1<<30;
			if(A[i]>R[i+1]) R[i]=min(R[i],A[i+1]);
			if(A[i]>A[i+1]) R[i]=min(R[i],R[i+1]);
		}
		
		M[ma][0]=L[ma];
		M[ma][1]=-1;
		for(i=ma+1;i<=N;i++) {
			M[i][0]=1<<30;
			M[i][1]=-1;
			
			if(A[i]<A[i-1]) M[i][0]=min(M[i][0],M[i-1][0]);
			if(A[i]<M[i-1][1]) M[i][0]=min(M[i][0],A[i-1]);
			if(A[i]>A[i-1]) M[i][1]=max(M[i][1],M[i-1][1]);
			if(A[i]>M[i-1][0]) M[i][1]=max(M[i][1],A[i-1]);
			if(M[i][1]>R[i]) ret++;
		}
		
	}
	cout<<ret<<endl;
	
}

まとめ

こういうのわかってしまえばすんなりなんだけどね。