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;
}