珠海网站建设公司哪个好,做标书的视频网站,扬州百度推广公司,杭州网站建设出 名考察异或运算以及前缀和
题意大概#xff1a;给你一个长度为n的a数组#xff0c;一个长度为n的01字符串#xff0c;会询问q次 当x的值为1 给出 l r 将 l r 区间中的0 改变为1#xff0c;1改变为0 。当x的值为2是 若随后的数为0 则输出当前字符串中 是0 的a数组中的数异或 … 考察异或运算以及前缀和
题意大概给你一个长度为n的a数组一个长度为n的01字符串会询问q次 当x的值为1 给出 l r 将 l r 区间中的0 改变为11改变为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[]数组的异或值当x2 是 直接输出num1或num2看所求是什么就求什么当x1时 就求出 l~r之间的数pre[r]^per[l-1]的异或值y 然后 更新num1^y,num2^y。因为相同的数异或为00与任何数异或都是不改变原来的数
例如
5
1 2 3 4 5
1 3 0 4 1 当前异或的前缀和
0 1 0 0 0
若 l2 r4
则 ypre[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
num1num1^ya1^a3^a4^a5^a2^a3^a4a1^a2^a5 相当于抵消了 原来出现过 在出现一遍抵消了 没有出现的没有抵消 就相当与1变成0 0变成1
#includeiostream
#includealgorithm
#includecstring
#includevector
using namespace std;
typedef long long ll;
const int N5e510;
int a[N];
int pre[N];
vectorintv;
int main()
{int t;cint;while(t--){v.clear();int n;cinn;memset(a,0,sizeof a);memset(pre,0,sizeof pre);int num10,num20;for(int i1;in;i) cina[i];string s1,s;cins1;s s1;for(int i1;in;i){if(i1) 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;cinq;while(q--){int x;cinx;if(x2){int num;cinnum;if(num0) v.push_back(num1);else v.push_back(num2);}else{int l,r;cinlr;int numpre[r]^pre[l-1];num1^num;num2^num;}}for(int i0;iv.size();i) coutv[i] ;coutendl;}return 0;
}
