https://torus711.hatenablog.com/entry/2024/11/25/185445

問題文

　https://atcoder.jp/contests/abc381/tasks/abc381_e

問題概要

　1, 2, / からなる長さ $n$ の文字列 $S$ が与えられる．以下のクエリを $q$ 個処理せよ：

整数 $l, r$ が与えられる．$S$ の $l$ 文字目から $r$ 文字目を取り出してできる文字列の（連続とは限らない）部分列であって，次の条件を満たすものの内最長なものの長さはいくらか？
- 当該部分列は，ある非負整数 $c$ について，$c$ 個の 1，$1$ 個の /，$c$ 個の 2 をこの順に連結して構成できる文字列と一致する．

制約

$1 \leq n \leq 10^5$
$1 \leq q \leq 10^5$

準備

　$S$ の $l$ 文字目から $r - 1$ 文字目を取り出して得られる部分文字列を $S[ l, r )$ と書くことにします．また，（実際の入力とは異なりますが）区間は一貫して右半開区間で扱うことにします．

解法

　（条件を満たす部分列の長さは奇数になりますが，）$3$ 以上の奇数 $k $ について，条件を満たす $k $ 文字の部分列をとれるならば，その両端をぞれぞれ取り除くことで $k - 2$ 文字で条件を満たす部分列をとるることができ，逆に，条件を満たす $k $ 文字の部分列が存在しないならば，$k + 2$ 文字で条件を満たす部分列をとることもできません．この単調性から，二分法できる言い換えをできればうれしくなれそうです．
　簡単のため，解の長さ自体ではなく 1, 2 が連続する個数 $c$ に着目し，ある固定された $c$ について条件を満たす部分列をとれるか否か判定することを考えます．条件を満たす部分列において 1 は左側にまとまって出現するため，$S[ l, r )$ においてより左にあるものから優先して部分列に含めた方が /, 2 をとってくる位置の選択肢を狭めずに済むのでよいです．よって，$S[ l, x )$ が 1 を $c$ 個以上含むような最小の $x$ について，1 は $S[ l, x )$ から，2, / は $S[ x, r )$ からとってくればよいということになります．2 についても同様で，$S[ y, r )$ が 2 を $c$ 個以上含むような最大の $y$ について，2 は $S[ y, r )$ から，1, / は $S[ l, y )$ からとってくればよいということになります．以上をまとめると，

1 は $S[ l, x )$ からとる．
2 は $S[ y, r )$ からとる．
/ は $S[ x, y )$ からとる．

ということになります．ある $c$ が feasible か否かは，その $c$ によって一意的に定まる $x, y$ で得られる $S[ x, y )$ 内に / が $1$ つ以上あるかどうかで判定できます．区間内に出現する特定の文字の出現回数を数えることで $x, y$ も二分法で求めることができるので，$c$ に関する二分法の内側で $x, y$ に関する二分法を行う二重の二分法で問題を解くことができます．
　判定に使っているのはいずれも「与えられた区間内に出現する特定の文字の個数を数える」という操作で，文字種が $3$ しか無いので各文字について累積和を用いて個数を求められるようにしておけば $O( 1 )$ 時間にできます．具体的には，例えば 1 であれば
\begin{equation*}
A_i = \begin{cases}
1 & \text{($S_i = 1$)} \\
0 & \text{(otherwise)}
\end{cases}
\end{equation*}
という列を作って累積和をとることで，区間内に出現する 1 の個数を数えることができます．
　上記のアルゴリズムは累積和をとる処理に $\Theta( n )$ 時間がかかり，二重の二分法 $q$ 回に $O( q \log^2 n )$ 時間がかかるので，まとめれば $O( n + q \log^2 n )$ 時間のアルゴリズムとなります．

コード

template < typename Num, typename F >
Num binary_method( const F &f, Num ok, Num ng )
{
	while ( 1 < abs( ok - ng ) )
	{
		const Num mid = ( ok + ng ) / 2;
		( f( mid ) ? ok : ng ) = mid;
	}
	return ok;
}

template < typename T >
struct Psum
{
	std::vector< T > psum;

	Psum( const std::vector< T > &A ) : psum( 1 )
	{
		std::partial_sum( std::begin( A ), std::end( A ),
				std::back_inserter( psum ) );
		return;
	}

	T operator[]( const int i ) const
	{
		return psum[ i + 1 ];
	}

	T sum( const int l, const int r ) const
	{
		return psum[r] - psum[l];
	}
};

int main()
{
	IN( int, N, Q );
	IN( string, S );

	VI A( N ), B( N ), C( N );
	REP( i, N )
	{
		if ( S[i] == '1' )
		{
			A[i] = 1;
		}
		if ( S[i] == '2' )
		{
			B[i] = 1;
		}
		if ( S[i] == '/' )
		{
			C[i] = 1;
		}
	}

	Psum psum1( A ), psum2( B ), psumS( C );

	REP( Q )
	{
		IN( int, L, R );
		--L;

		if ( !psumS.sum( L, R ) )
		{
			cout << 0 << '\n';
			continue;
		}

		const int C = binary_method( [&]( const int c ){
			const int l = binary_method( [&]( const int p ){
					return c <= psum1.sum( L, p );
					}, N, L );
			const int r = binary_method( [&]( const int p ){
					return c <= psum2.sum( p, R );
					}, 0, R );
			return 0 < psumS.sum( l, r );
		}, 0, N );

		cout << 2 * C + 1 << '\n';
	}

	cout << flush;

	return 0;
g