torus711 のアレ

主に競技プログラミングの問題について書きます

POJ 3368 : Frequent values

概要

n 項からなる単調非減少な数列 a が与えられる。
以下のようなクエリを処理せよ。

  • 区間 [ l, r ] の内で最も多く出現する数字の出現している個数を答えよ

解法

クエリを愚直に処理すると間に合わないので、Segment Tree を使って高速化します。
Segment Tree の各ノードには、以下の三つの情報をもたせます。
(「三つの Segment Tree を作る」とも言う)

  • そのノードの受け持つ区間内で最長の区間の長さ
  • 左端の区間の長さ
  • 右端の区間の長さ

木を初期化する際、末端ではこれらの値は全て 1 です。
それ以外の節については、次のようにします。

  • 左の子の右端の値と、右の個のの左端の値が等しい場合
    • 最長の区間の長さと、左の個の右端と右の個の左端を繋げたものの内、大きい方が最長の区間の長さ
  • 二つの子の左端の値が等しい場合
    • 左端区間に右の子の左端区間を繋げる
  • 二つの子の右端の値が等しい場合
    • 右端区間に左の子の右端区間を繋げる

クエリに答える際も同じような場合分けをして処理します。
値を三つ返さないといけないので、適当になんとかします。

コード

typedef vector<int> VI;

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

struct SegTree
{
	int n;
	// 最長の長さ、左端、右端、元の配列
	VI length, tol, tor, src;

	struct Res
	{
		int length, l, r;

		Res( int len = 0, int l = 0, int r = 0 ) : length( len ), l( l ), r( r )
		{
			return;
		}

		operator int () // int にキャストされたら最大値
		{
			return max( length, max( l, r ) );
		}
	};

	SegTree( int n, VI &src ) : n( n ),	length( n * 4 ), tol( n * 4 ), tor( n * 4 ), src( src )
	{
		init( 0, 0, n );

		return;
	}

	void init( int k, int l, int r )
	{
		if ( l + 1 == r ) // 区間の幅が 1 <=> 末端ノード
		{
			length[k] = tor[k] = tol[k] = 1;

			return;
		}

		int idx1 = k * 2 + 1, idx2 = k * 2 + 2, mid = ( l + r ) / 2;

		init( idx1, l, mid );
		init( idx2, mid, r );

		length[k] = max( length[ idx1 ], length[ idx2 ] );

		tol[k] = tol[ idx1 ];
		tor[k] = tor[ idx2 ];

		// 左の子の右端と右の子の左端
		if ( src[ mid - 1 ] == src[ mid ] )
		{
			length[k] = max( length[k], tor[ idx1 ] + tol[ idx2 ] );
		}

		// 子の左端同士
		if ( src[l] == src[ mid ] )
		{
			tol[k] += tol[ idx2 ];
		}

		// 子の右端同士
		if ( src[ mid - 1 ] == src[ r - 1 ] )
		{
			tor[k] += tor[ idx1 ];
		}

		return;
	}

	Res query( int a, int b )
	{
		return query( a, b, 0, 0, n );
	}

	Res query( int a, int b, int k, int l, int r )
	{
		int idx1 = k * 2 + 1, idx2 = k * 2 + 2, mid = ( l + r ) / 2;

		if ( b <= l || r <= a )
		{
			return Res();
		}
		else if ( a <= l && r <= b )
		{
			return Res( length[k], tol[k], tor[k] );
		}
		else
		{
			Res chl = query( a, b, idx1, l, mid );
			Res chr = query( a, b, idx2, mid, r );

			Res res( max( chl.length, chr.length ), chl.l, chr.r );

			// 左の子の右端と右の子の左端
			if ( src[ mid - 1 ] == src[ mid ] )
			{
				res.length = max( res.length, chl.r + chr.l );
			}

			// 子の左端同士
			if ( src[l] == src[ mid ] )
			{
				res.l += chr.l;
			}

			// 子の右端同士
			if ( src[ mid - 1 ] == src[r] )
			{
				res.r += chl.r;
			}

			return res;
		}
	}
};

int main()
{
	while ( true )
	{
		int n;
		scanf( " %d", &n );

		if ( !n )
		{
			break;
		}

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

		VI ary( n );

		REP( i, 0, n )
		{
			scanf( " %d", &ary[i] );
		}

		SegTree st( n, ary );

		REP( i, 0, q )
		{
			int l, r;
			scanf( " %d %d", &l, &r );

			l--;

			cout << st.query( l, r ) << endl;
		}
	}

	return 0;
}