AtCoder Beginner Contest 341, E : Alternating String

問題文

　https://atcoder.jp/contests/abc341/tasks/abc341_e

問題概要

　$0$ と $1$ からなる $n$ 要素の列 $S = S_1, S_2, \dots S_n$ ($S_i \in { 0, 1 }$) が与えられる．クエリが $q$ 個与えられるので，順に処理せよ．クエリは以下の 2 種類からなる：

• $( 1, l, r )$ : $l \leq i \leq r$ なる $i$ について，$$S_i \leftarrow 1 - S_i$$ と更新する*1．
• $( 2, l, r )$ : $l \leq i < r$ なる任意の $i$ について $$S_i \neq S_{ i + 1 }$$ かどうか判定する．

制約

• $1 \leq n, q \leq 5 \times 10^5$

解法

　前提として，反転や条件判定を愚直に処理すると最悪ケースで $\Theta( n q )$ 時間がかかって TLE するので，より高速な方法を考える必要があります．
　考察のために，クエリ 2 で判定に使う真偽値を並べた列を考えてみます．つまり，$n - 1$ 項ならなる列 $B$ であって
\begin{equation*}
B_i = S_i \neq S_{ i + 1 }
\end{equation*}
というようなものを作り，各クエリが $B$ の視点だとどうなるかを考えます．
　クエリ 1 については，$S_i$ と $S_{ i + 1 }$ の両方が反転しても $B_i$ の値が変化しないということに着目すると，$B$ の変化は
\begin{align*}
B_{ l - 1 } &\leftarrow 1 - B_{ l - 1 } && \text{($1 < l$)} \\
B_r &\leftarrow 1 - B_r && \text{($r < n$)}
\end{align*}
の高々 2 つです．また，クエリ 2 については
\begin{equation*}
\bigwedge_{ l \leq i < r } B_i
\end{equation*}
となります*2．
　さて，列上の 1 箇所を更新する処理と連続する部分列をある種の演算*3で畳み込む処理になったわけですが，これは Segment Tree を用いるとそれぞれ $O( \log n )$ 時間で実現できます．よってこの場合合計で $O( ( n + q ) \log n )$ 時間となり間に合います．
　実装については，Segment Tree は AtCoder Library (ACL) に含まれているので，これを利用することで簡単になります．

コード

#include <atcoder/segtree>
using namespace atcoder;

bool land( bool a, bool b )
{
	return a && b;
}

bool t()
{
	return true;
}

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

	segtree< bool, land, t > segtree( N - 1 );
	REP( i, N - 1 )
	{
		segtree.set( i, S[i] != S[ i + 1 ] );
	}

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

		if ( T == 1 )
		{
			if ( L )
			{
				segtree.set( L - 1, !segtree.get( L - 1 ) );
			}
			if ( R < N )
			{
				segtree.set( R - 1, !segtree.get( R - 1 ) );
			}
		}
		else
		{
			cout << ( segtree.prod( L, R - 1 ) ? "Yes" : "No" ) << '\n';
		}
	}
	
	cout << flush;

	return 0;
}

*1:$0$ と $1$ を反転する．

*2:$\bigwedge$ は論理積を表します．

*3:モノイドを作れる演算．