POJ 3264 : Balanced Lineup

問題文

http://poj.org/problem?id=3264

概要

N 項からなる数列が与えられる。
続いて、以下のクエリが Q 個与えらえるので全て処理せよ。

• 区間 [ l, r ] の最大値と最小値の差を出力せよ

解法

愚直に処理すると O( Q N ) で間に合いません。
区間毎の最小値/最大値を保持する Segment Tree を使うと O( Q log N ) になって間に合います。
cin 使ったら遅くて TLE 量産したのが私です。

コード

using namespace std;

typedef vector<int> VI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

struct SegTree
{
	int N, n, ie;
	VI data, src;

	template < typename C >
	SegTree( int n, int ie, VI &ary, C comp ) : N( 1 ), n( n ), ie( ie ), data( n * 4 ), src( ary )
	{
		while ( N < n )
		{
			N *= 2;
		}

		init( 0, 0, n, comp );

		return;
	}

	template < typename C >
	void init( int k, int l, int r, C comp )
	{
		if ( r - l == 1 )
		{
			data[k] = src[l];
		}
		else
		{
			int mid = ( l + r ) / 2;

			init( k * 2 + 1, l, mid, comp );
			init( k * 2 + 2, mid, r, comp );

			data[k] = min( data[ k * 2 + 1 ], data[ k * 2 + 2 ], comp );
		}

		return;
	}

	template < typename C >
	int query( int a, int b, C comp )
	{
		return query( a, b, 0, 0, n, comp );
	}
	
	template < typename C >
	int query( int a, int b, int k, int l, int r, C comp )
	{
		if ( b <= l || r <= a )
		{
			return ie;
		}
		else if ( a <= l && r <= b )
		{
			return data[k];
		}
		else
		{
			int mid = ( l + r ) / 2;

			int left = query( a, b, k * 2 + 1, l, mid, comp );
			int right = query( a, b, k * 2 + 2, mid, r, comp );
	
			return min( left, right, comp );
		}
	}
};

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

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

	scanf(" %d %d", &n, &q );

	VI as( n );

	REP( i, 0, n )
	{
		//cin >> as[i];
	
		scanf(" %d", &as[i] );
	}

	SegTree stMin( n, INT_MAX, as, less<int>() ), stMax( n, INT_MIN, as, greater<int>() );

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

		//cin >> l >> r;
		scanf(" %d %d", &l, &r );

		// 0-indexed の [ l, r ) に
		l--;

		cout << stMax.query( l, r, greater<int>() ) - stMin.query( l, r, less<int>() ) << endl;
	}

	return 0;
}