E - TrBBnsformBBtion
[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;
}
}