問題概要

'A'と'B'からなる文字列$S,T$に対して，次の操作を任意の順番で何回でも行える．

文字列$S,T$($1 \leq |S|, |T| \leq 10^{5}$)が与えられるので，次の$q$個 ($ 1 \leq q \leq 10^{5}$) のクエリに答えよ．

解法

解説AC．部分文字列について「'A'を1，'B'を2に変換し，それらを合計して3で割ったあまり」が等しければ変換可能．累積和を計算しておくと高速化できる．

天才変形に見えてしまって困ったが，kmjpさんの記事を読むと典型テクニックっぽいことが分かる．以下では記事を参考にしながらこのテクニックをまとめてみる． (不備があれば教えてもらえるとありがたいです......)

$S$を適当な集合とする．「$a \in S$を，操作の集合$M= \lbrace m|m: S \rightarrow S \rbrace $ によって $b\in S$ にできますか」問題を高速に解くテクニックとして，次のものは汎用的に使えそう．

評価用写像$f:S\rightarrow\mathbb{N} \ s.t. \ \forall m\in M,f(a)=f(m(b))$を用意する
- 計算が十分に高速である必要がある
$L$を $ M $ の元から成る操作の順列(うまい説明ができない...)として，次が成り立つことを確認する: $$ \forall (x,y)\ s.t.\ x\in S \land y \in S \land f(x)=f(y) , \ \exists L s.t. L(x)=y$$

(評価値が同じであれば相互に変換可能であることを示している)

このとき，$f(x)=f(y) \Rightarrow \exists L\ s.t.\ L(x)=y $であり，$f(x)\neq f(y) \Rightarrow \nexists L \ s.t.\ L(x)=y$である．$f(x)$の計算によって操作方法の存在判定を高速に行うことができる．

$$ \forall (x,y) \ s.t.\ x\in S \land y \in S \land f(x)\neq f(y) , \ \nexists L \ s.t. \ L(x)=y$$

も成立しているか確認しないとまずそうだが，$f(x)\neq f(y)$であれば，

$$\forall L,f(x)=f(L(x))\neq f(y) (\because fの定義) \ \therefore \nexists L \ s.t.\ L(x)=y$$ が成り立つので大丈夫．

この問題について適用すると，

$S:=$'A'と'B'からなる文字列の集合
$M:=$問題文中の2つの操作からなる集合
$f:=$(文字列中の'A'の数+文字列中の'B'の数$\times 2$) $mod\ 3$
- $\forall m\in M,f(x)=f(m(x))$を満たしている
- 評価値の計算は累積和を使うことで高速化できる
公式editorialを読むと2番の命題は真であることが分かる

である．

慣れてないと$f$を作るのが辛そう．

~~mathjaxを導入したんですが，「文字列$S$，$T$($1\leq|S|,|T|\leq 10⁵ $)」みたいになってしまうので解決策をお持ちの方は教えてください...~~ 解決しました