E. Data Structures Fan(思维 + 异或前缀和)

Problem - E - Codeforces

给你一个整数数组 a1, a2,..., an，以及一个由 n 个字符组成的二进制字符串† s。

Augustin 是一个数据结构的爱好者。因此，他请你实现一个可以回答 q 个查询的数据结构。这里有两种类型的查询：

Plain Text

"1 l r" (1≤l≤r≤n) — 将 l ≤ i ≤ r 的每个字符 si 替换为其相反值。也就是，将所有的 0 替换为 1，将所有的 1 替换为 0。
"2 g" (g∈{0,1}) — 计算所有满足 si=g 的索引 i 对应的数字 ai 的按位异或（bitwise XOR）值。注意，空集合的异或值被认为是等于 0。

请帮助 Augustin 回答所有的查询！

例如，如果 n=4，a=[1,2,3,6]，s=1001，考虑以下一系列查询：

Plain Text

"2 0" — 我们对于满足 si=0 的索引 i 感兴趣，因为 s=1001，这些索引是 2 和 3，所以查询的答案将是 a2⊕a3=2⊕3=1。
"1 1 3" — 我们需要将字符 s1,s2,s3 替换为它们的相反值，所以在查询之前 s=1001，在查询之后：s=0111。
"2 1" — 我们对于满足 si=1 的索引 i 感兴趣，因为 s=0111，这些索引是 2, 3 和 4，所以查询的答案将是 a2⊕a3⊕a4=2⊕3⊕6=7。
"1 2 4" — s=0111 → s=0000。
"2 1" — s=0000，没有满足 si=1 的索引，所以由于空集合的异或值被认为是等于 0，这个查询的答案是 0。

† 二进制字符串是只包含字符 0 或 1 的字符串。

输入

输入的第一行包含一个整数 t (1≤t≤10^4) — 测试用例的数量。

接下来是每个测试用例的描述。

每个测试用例描述的第一行包含一个整数 n (1≤n≤10^5) — 数组的长度。

测试用例的第二行包含 n 个整数 a1,a2,...,an (1≤ai≤10^9)。

测试用例的第三行包含长度为 n 的二进制字符串 s。

测试用例的第四行包含一个整数 q (1≤q≤10^5) — 查询的数量。

测试用例的后续 q 行描述了查询。每个查询的第一个数字 tp ∈ {1,2}，表示查询的类型：如果 tp=1，则紧随其后是两个整数 1≤l≤r≤n，表示应该使用参数 l,r 执行类型 1 的操作；如果 tp=2，则紧随其后是一个整数 g∈{0,1}，表示应该使用参数 g 执行类型 2 的操作。

保证所有测试用例中 n 的总和不超过 10^5，并且 q 的总和不超过 10^5。

输出

对于每个测试用例中的每个类型 2 的查询，输出相应查询的答案。

示例

输入

5 5 1 2 3 4 5 01000 7 2 0 2 1 1 2 4 2 0 2 1 1 1 3 2 1 6 12 12 14 14 5 5 001001 3 2 1 1 2 4 2 1 4 7 7 7 777 1111 3 2 0 1 2 3 2 0 2 1000000000 996179179 11 1 2 1 5 1 42 20 47 7 00011 5 1 3 4 1 1 1 1 3 4 1 2 4 2 0

输出

3 2 6 7 7 11 7 0 0 16430827 47

注意

让我们分析第一个测试用例：

"2 0" — 对于满足 si=0 的索引 i，我们感兴趣的是这些查询的答案将是 a1⊕a3⊕a4⊕a5=1⊕3⊕4⊕5=3。 "2 1" — 对于满足 si=1 的索引 i，我们感兴趣的是这些查询的答案将是 a2=2。 "1 2 4" — 我们需要将字符 s2,s3,s4 替换为它们的相反值，所以在查询之前 s=01000，在查询之后：s=00110。 "2 0" — 对于满足 si=0 的索引 i，我们感兴趣的是这些查询的答案将是 a1⊕a2⊕a5=1⊕2⊕5=6。 "2 1" — 对于满足 si=1 的索引 i，我们感兴趣的是这些查询的答案将是 a3⊕a4=3⊕4=7。 "1 1 3" — s=00110 → s=11010。 "2 1" — 对于满足 si=1 的索引 i，我们感兴趣的是这些查询的答案将是 a1⊕a2⊕a4=1⊕2⊕4=7。

题解:
本来看到区间修改,一直在想用什么数据结构,最后也没想出来

赛后看别人代码,发现这是一个思维题

我们只需要记录,异或前缀和,初始为0位置的异或和,为1位置的异或和即可

如果要修改区间,根据异或前缀和我们可以很快求出那一段区间的异或和 t

s0 ^= t

s1 ^= t

为啥这样就可以?

我们以1的举例,t中可能会有此时为0,和此时为1的异或和,由于之前已经计算了,为一时的异或,再次异或,就消去了,为0的之前没有异或,异或一下刚好,而这个过程不就是反转的过程吗

为0同理

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> PII;
int a[100050];
int pre[100054];
void solve()
{int n;cin >> n;for(int i = 1;i <= n;i++){cin >> a[i];}string s;cin >> s;vector<int> ans(10);s = "?" + s;for(int i = 1;i <= n ;i++){ans[s[i] - '0'] ^= a[i];pre[i] = pre[i - 1]^a[i];}int q;cin >> q;while(q--){int op,l,r;cin >> op >> l;if(op == 2){cout << ans[l] <<" ";}else{cin >> r;int t = pre[r]^pre[l - 1];ans[0] ^= t;ans[1] ^= t;}}cout <<"\n";
} 
signed main()
{int t = 1;ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> t ;	while(t--){solve();}
}