Data Structures Fan(cf)
考察异或运算以及前缀和
题意大概：给你一个长度为n的a数组，一个长度为n的01字符串，会询问q次 当x的值为1 给出 l r 将 l r 区间中的0 改变为1，1改变为0 。当x的值为2是 若随后的数为0 则输出当前字符串中 是0 的a数组中的数异或 并输出结果 是1 则输出a数组的下标对应的数异或 多组输入
输入样例
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
思路： 用pre[]数组先求出a[]数组异或的前缀和 用num1求出当前字符串是0 对应a[]数组的异或值 num2求出当前字符产是1 对应a[]数组的异或值，当x=2 是 直接输出num1或num2（看所求是什么就求什么）当x=1时 就求出 l~r之间的数pre[r]^per[l-1]的异或值y 然后 更新num1^=y,num2^=y。（因为相同的数异或为0，0与任何数异或都是不改变原来的数）
例如
5
1 2 3 4 5
1 3 0 4 1 当前异或的前缀和
0 1 0 0 0
若 l=2 r=4
则 y=pre[1]^pre[4]=a1^a1^a2^a3^a4 a1与a1异或为0 抵消了 故可以这样求出 l~r之间的异或值
此时 S变为 0 0 1 1 0
num1原来为 a1^a3^a4^a5 现在应为 a1^a2^a5
num1=num1^y=a1^a3^a4^a5^a2^a3^a4=a1^a2^a5 相当于抵消了 原来出现过 在出现一遍抵消了 没有出现的没有抵消 就相当与1变成0 0变成1
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
typedef long long ll;
const int N=5e5+10;
int a[N];
int pre[N];
vector<int>v;
int main()
{int t;cin>>t;while(t--){v.clear();int n;cin>>n;memset(a,0,sizeof a);memset(pre,0,sizeof pre);int num1=0,num2=0;for(int i=1;i<=n;i++) cin>>a[i];string s1,s;cin>>s1;s=" "+s1;for(int i=1;i<=n;i++){if(i==1) pre[i]=a[i];else pre[i]=pre[i-1]^a[i];if(s[i]=='0') num1^=a[i];else if(s[i]=='1') num2^=a[i];}int q;cin>>q;while(q--){int x;cin>>x;if(x==2){int num;cin>>num;if(num==0) v.push_back(num1);else v.push_back(num2);}else{int l,r;cin>>l>>r;int num=pre[r]^pre[l-1];num1^=num;num2^=num;}}for(int i=0;i<v.size();i++) cout<<v[i]<<" ";cout<<endl;}return 0;
}