Atcoder ARC071E TrBBnsformBBtion

发布时间 2023-06-13 09:14:05作者: lhzawa

考虑把所有的 B 都变为 A 来处理,因为 AB 是可以互换的,就只需要判断 \(s_{a_i\cdots b_i}\)\(t_{c_i\cdots d_i}\) 对应的 A 的个数能不能在操作后相等。
A 的个数前缀和维护即可。

考虑 1 操作,发现其实可以 \(1\)A 变为 \(2\)B 再变为 \(4\)A,即 A 的个数 \(+3\)
考虑 2 操作,其就是 A 的个数 \(-3\)
所以发现操作只有 \(+3\)\(-3\),所以若两部分个数差为 \(3\) 的倍数即合法。

时间复杂度 \(O(|S| + |T| + Q)\)

// lhzawa(https://www.cnblogs.com/lhzawa/)
// Problem: E - TrBBnsformBBtion
// Contest: AtCoder - AtCoder Regular Contest 071
// URL: https://atcoder.jp/contests/arc071/tasks/arc071_c
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
char s[N], t[N];
int sw[N], tw[N];
int main() {
	scanf("%s%s", s + 1, t + 1);
	int n = strlen(s + 1), m = strlen(t + 1);
	for (int i = 1; i <= n; i++) {
		sw[i] = sw[i - 1] + (s[i] - 'A' + 1);
	}
	for (int i = 1; i <= m; i++) {
		tw[i] = tw[i - 1] + (t[i] - 'A' + 1);
	}
	int q;
	scanf("%d", &q);
	for (; q; q--) {
		int sl, sr, tl, tr;
		scanf("%d%d%d%d", &sl, &sr, &tl, &tr);
		printf("%s\n", abs((sw[sr] - sw[sl - 1]) - (tw[tr] - tw[tl - 1])) % 3 == 0 ? "YES" : "NO");
	}
	return 0;
}