[Q] https://atcoder.jp/contests/arc071/tasks/arc071_c
文字列を消しに消した場合、AかBか_の3通りに落ち着く。
残り文字が等しい場合、文字列を復元できるので、合致することがわかる。

毎回クエリ文字列を操作するのはTLEしそう。高速化のために、累積和をとってみる。

入力例
BBBAAAABA

累積。
B = B
BB = A
BBB = _
BBBA = (BBB)+A = A 
Q. 高速化できる？
A. 1つ前の状態に置換できそう
BBBAA = (BBBA)+A = AA = B
BBBAAA = (BBBAA)A = BA = BBB = _

・累積を下段にとる
BBBAAAABA
BA_AB_A_A

Q. 区間が与えられた場合どうする？
A. 2 5を考える。
(1) = Bで、
(1 5) = Bとわかっている。
(1) + (2 5) = (1 5)
 B  +   X   =   B
        X   = B - B = _

(2 5) = BBAA = _ でたしかにあってる。

A=1, B=2, _=0と置き換えて、3進数の計算を行えばうまくいきそうな感じ。

実装。

string S, T;
ll acc_s[100010];
ll acc_t[100010];

int main(){
 cincout();
 
 ll Q;
 cin >> S >> T >> Q;
 ll sz = S.size();
 ll tsz = T.size();
 rep(i, sz){
	  if (S[i] == 'A') acc_s[i] = 1;
	  if (S[i] == 'B') acc_s[i] = 2;
 }
 rep(i, sz-1) ( acc_s[i+1] += acc_s[i]) %= 3;

 rep(i, tsz){
	  if (T[i] == 'A') acc_t[i] = 1;
	  if (T[i] == 'B') acc_t[i] = 2;
 }
 rep(i, tsz-1) ( acc_t[i+1] += acc_t[i]) %= 3;

 rep(i, Q){
	  ll a, b, c, d;
	  cin >> a >> b >> c >> d;
	  --a, --b, --c, --d;
	  ll s=acc_s[b];
	  if (a>0) ( s = s-acc_s[a-1] + 3) %= 3;
	  ll t=acc_t[d];
	  if (c>0) ( t = t-acc_t[c-1] + 3) %= 3;
	  if (s==t) cout << "YES" << endl;
	  else cout << "NO" << endl;
 }
}

https://atcoder.jp/contests/arc071/submissions/26229164