Codeforces #171 Div2. C. Ladder

さてここからが本番。
http://codeforces.com/contest/279/problem/C

問題

はしご状配列とは、先頭から途中までの要素が単調増加で、その後最後まで単調減少になる数列である。
数値配列が与えられ、またその後始点・終点を示すクエリが与えられる。
数値配列のうち、クエリ中の値を始点・終点とする部分配列がはしご状か否かを答える。

解法

先に前処理として、数列の各要素に対しどこまでの要素が単調増加かを先頭→終端方向と終端→先頭の両方向で求めておく。
クエリ中の始点・終点について、始点から終端方向へたどった単調増加の最後の要素と、終点から先頭方向へたどった単調増加の最後の要素が一致すればはしご状になる。

int N,M;
int A[100001];
int UP[100001],DO[100001];

void solve() {
	int f,r,i,j,k,l,x,y;
	int ma=0;
	
	N=GETi();
	M=GETi();
	FOR(i,N) A[i]=GETi();
	
	i=0;
	FOR(j,N-1) if(A[j]>A[j+1]) while(i<=j) UP[i++]=j;
	while(i<=N-1) UP[i++]=N-1;
	
	i=N-1;
	for(j=N-1;j>=1;j--) if(A[j]>A[j-1]) while(i>=j) DO[i--]=j;
	while(i>=0) DO[i--]=0;
	
	FOR(i,M) {
		x=GETi()-1;
		y=GETi()-1;
		_P("%s\n",(UP[x]>=y || DO[y]<=x || UP[x]==DO[y] || (UP[x]>DO[y] && A[UP[x]]==A[DO[y]]))?"Yes":"No");
	}
	
	return;
}

まとめ

これはすんなり思いつけて良かった。