\(Solution\)
性质题。
\(\mathcal{part\ 1}\)
\(n\leq 10^5\) 的数据范围一定会让人敏锐的想到线段树,本题可以使用线段树求解,但是细节很多,在考场上很难调对。
\(\mathcal{part\ 2}\)
考虑异或的性质:偶数次异或同一个数,对答案没有影响。证明请读者自行思考,过程并不繁琐。
再次观察操作 \(1\)。对于取反操作,被选的数字变为不选,不选的数字变为被选的。可以通过直接异或上区间异或和得到。通过异或的性质我们可以得到一个数异或自己奇数次得到的答案是自己,偶数次是 \(0\),恰好满足。
分别维护“\(0,1\) 区间” ,使它们的异或和分别等于 \(b0,b1\),然后用刚才提到的方法维护即可。
那么对于操作 \(2\),直接输出 \(b0\) 或 \(b1\)。
复杂度 \(\Theta(\sum n)\)。
\(\mathcal{Code}\)
#define int long long
const int N = 1e6 + 5;
namespace Jelly {
int n, ans = 0, a[N], q, b[N], b1, b0;
char s[N];
int main() {
Read(n);
b0 = b1 = 0;
for(int i = 1; i <= n; i ++) Read(a[i]);
Read(s, q);
for(int i = 1; i <= n; i ++) {
b[i] = b[i - 1] ^ a[i];
b0 = b0 ^ (s[i - 1] == '1' ? 0ll : a[i]);
b1 = b1 ^ (s[i - 1] == '1' ? a[i] : 0ll);
}
while(q --) {
int opt, x, y;
Read(opt);
if(opt == 2) {
Read(x);
if(x == 0) Write(b0, ' ');
else Write(b1, ' ');
}
else Read(x, y), b0 ^= (b[y] ^ b[x - 1]), b1 ^= (b[y] ^ b[x - 1]);
}
Writeln();
return 0;
}
}
signed main() {
int T = 1;
Read(T);
while(T --) Jelly::main();
return 0;
}