AtCoder Regular Contest 071：E - TrBBnsformBBtion
問題
解法
各クエリで与えられる部分文字列を A だけの最も短い文字列にすることを考える．まず，部分文字列中の B を全て AA に変換し，残った A だけの文字列のうち AAA と 3 つ A が並んでいる箇所は空文字列に出来るので出来るだけ AAA を消していく．そうすると，結果 (空文字列, AAA としてもいい), A, AA の 3 パターンになる．逆に，空文字列を AAA ととらえると，この 3 パターンから任意の文字列を作ることが出来る．各クエリで与えられる S の部分文字列と T の部分文字列がこの 3 パターンの中でどれに当てはまるかは，前計算で累積和を取っておくことで任意の区間の A, B の個数を知ることが出来るので O(1) で分かる．最後にパターンが一致しているか，すなわち，A の個数が等しいかどうかを判定し，等しければ YES，等しくなければ NO となる．
解答
