题解 | #串串串#

这里提供另一种做法：

不难发现答案就是 $aa$ 和 $bb$ 异或起来 $11$ 的个数，如果为奇数就为 $11$, 为偶数就为 $00$。

发现奇数个 $11$ 异或起来正好等于 $11$，偶数个异或起来等于 $00$，所以直接两个区间的异或值异或起来就是答案。

复杂度 $O(m+n)O(m\; +\; n)$

code

/*
work by:Ariel_
Sorce:
Knowledge:
Time:
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <algorithm>
#define ll long long
#define rg register
using namespace std;
const int MAXN = 2e5 + 5;
int read(){
    int x = 0,f = 1; char c = getchar();
    while(c < '0'||c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') {x = x*10 + c - '0'; c = getchar();}
    return x*f;
}
int preb[MAXN], prea[MAXN], n, m, a[MAXN], b[MAXN], Q;
char s[MAXN], t[MAXN];
int main(){
   n = read(), m = read();
   scanf("%s%s", s + 1, t + 1);
   for (int i = 1; i <= n; i++) a[i] = s[i] - '0', prea[i] = prea[i - 1] ^ a[i];
   for (int i = 1; i <= m; i++) b[i] = t[i] - '0', preb[i] = preb[i - 1] ^ b[i];
   Q = read();
   while(Q--) {
   	 int l = read(), r = read(), L = read(), R = read();
   	 int ret = prea[r] ^ prea[l - 1], res = preb[R] ^ preb[L - 1];
   	 int Ans = ret ^ res;
   	 cout<<Ans<<"\n";
   }
   puts("");
   return 0;
}