AtCoder Regular Contest 071 E TrBBnsformBBtion
A～BB, B～AA, AAA～(空文字), BBB～(空文字) と編集可能とする。
文字列SとTが与えられたときに、クエリS[a, b] T[c, d]が同値かどうか答えよ。
ただし、文字列が同値とは編集を繰り返して別の文字列にたどり着くことと定義する。
同値類の問題なので代表元を見つければよい。簡単なのはAだけで表される最短文字列。つまり全部Aにして、AAA～(空文字)を使って最短にしてしまえばよい。
ちなみにそういう同値類は空文字、A, AAの3種類しかない。
S[a, b] T[c, d]のような部分文字列がその3種類のいずれかを判定する必要があるが、
これはつまり区間[a, b]や区間[c, d」のAとBの数がカウントできれば、(A+B*2) mod 3が同値類になり、これの一致を見れば良い。
なのでBのところだけ1、あとは0であるような配列のRange sum queryをSegtree or BITで実装すると、クエリの応答がO(log(N))になり間に合う。
