【AtCoder Regular Contest 071 E】TrBBnsformBBtion | Mrsrz's blog

性质题，前缀和。

题目大意：

给定两个只由 A 和 B 组成的字符串 $s$ 和 $t$，有以下几种操作：

1. 将一个 A 变成 BB。
2. 将一个 B 变成 AA。
3. 删除一个 AAA。
4. 删除一个 BBB。

每次询问给出 $l_1,r_1,l_2,r_2$，问 $s(l_1,r_1)$ 能否通过操作变成 $t(l_2,r_2)$。$s(l,r)$ 表示取字符串 $s$ 的 $l\sim r$ 字符组成的子串。

题解：

我们先看看它能有什么有用的变化组合。

AA$\rightarrow$BBBB$\rightarrow$B

同理 BB 也可以变成 A。

也就是说我们可以把字符串中所有 A 都变成 BB。这并不影响结果。

那么我们现在有一个长度为 $n$ 的全 B 串，要求变为长度为 $m$ 的全 B 串。

如果 $n\geq m$，则只需要 $n-m\equiv 0\pmod 3$ 即可。

我们还有如下变化：

B$\rightarrow$AA$\rightarrow$BBBB

也就是说只要字符串不为空，也可以无端变出三个 B 来。

那么只需要 $|n-m|\equiv 0\pmod 3$ 即可。

用前缀和维护前缀 A 和 B 的个数即可。

Code：

#include<cstdio>
const int N=1e5+5;
int q,A[N],B[N],l,r,L,R;char s[N];
int main(){
    scanf("%s",s+1);for(int i=1;s[i];++i)A[i]=A[i-1]+s[i]-64;
    scanf("%s",s+1);for(int i=1;s[i];++i)B[i]=B[i-1]+s[i]-64;
    for(scanf("%d",&q);q--;)scanf("%d%d%d%d",&l,&r,&L,&R),puts((A[r]-A[l-1])%3==(B[R]-B[L-1])%3?"YES":"NO");
    return 0;
}