Codeforces #171, C : Ladder

問題文

http://codeforces.com/contest/279/problem/C

概要

n 項からなる数列が与えられる。
この数列に対するクエリとして、二つの整数 l, r をとって区間 [ l, r ] が Ladder であるかどうかを判定する。
区間が Ladder であるとは、その区間を表す部分列 b が次の条件を満たす場合である。

• を満たす整数 が存在する（ k は b の項数）

m 個のクエリが与えられるので、これを処理せよ。

解法

区間 [ l, r ] が Ladder である条件は次のように言い換えることができます。

• ある増加部分とそれに続く減少部分を連結した区間の中に含まれる

このような部分を全て求め、各インデクスについてどの区間に属するか（複数も有り得る）を前計算し、その結果を segments としておきます。
すると、segments[l] と segments[r] に共通部分があるかどうかで判定できます。

コード

typedef vector<int> VI;
typedef vector<VI> VVI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )
#define ALL( c ) (c).begin(), (c).end()
#define PB( n ) push_back( n )

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n, q;
	cin >> n >> q;

	VI as( n );
	FOR( a, as )
	{
		cin >> a;
	}

	VVI segments( n );
	int prev = 0, starts = 0, segnum = 0;
	bool down = false;
	REP( i, 1, n )
	{
		if ( down && as[ i - 1 ] < as[i] )
		{
			REP( j, prev, i )
			{
				segments[j].PB( segnum );
			}
			segnum++;
			down = false;
			prev = starts;
		}

		if ( as[ i - 1 ] != as[i] )
		{
			starts = i;
		}

		if ( as[ i - 1 ] > as[i] )
		{
			down = true;
		}
	}
	REP( j, prev, n )
	{
		segments[j].PB( segnum );
	}

	REP( i, 0, q )
	{
		int l, r;
		cin >> l >> r;
		l--;
		r--;

		VI intersect;
		set_intersection( ALL( segments[l] ), ALL( segments[r] ), back_inserter( intersect ) );

		cout << ( intersect.empty() ? "No" : "Yes" ) << endl;
	}		

	return 0;
}