概要
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; }