CF1872E-Data Structures Fan
题目大意
给你一个长度为n nn的序列，每个数字有一个对应的0 00或1 11。现在你有q qq次操作。
1 l r 1\space l\space r1lr将l ll到r rr区间内的所有数的0 00,1 11取反。
2 x 2 \space x2x统计所有对应数字为x xx的数的异或和。
题解
对于1 11操作的维护。我们先将序列求前缀异或和，然后再跟所有数的初始对应值，分类异或和存进x o r 1 , x o r 0 xor1,xor0xor1,xor0两个变量中。这样每次操作，我们只需要用前缀异或和得到l , r l,rl,r区间内的异或和，对应异或上x o r 1 , x o r 0 xor1,xor0xor1,xor0就可以完成0 , 1 0,10,1翻转的操作。
对于2 22操作的查询，就只要对应输出x o r 1 , x o r 0 xor1,xor0xor1,xor0的值即可。
#include<bits/stdc++.h>#defineiosios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#defineumapunordered_map#defineendl'\n'usingnamespacestd;usingi128=__int128;constintmod=1e9+7;template<typenameT>voidread(T&x){x=0;intf=1;charc=getchar();for(;!isdigit(c);c=getchar())if(c=='-')f=-1;for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);x*=f;}template<typenameT>voidprint(T x){if(x<0){putchar('-');x=-x;}if(x>9)print(x/10);putchar(x%10+'0');}#defineintlonglongconstintN=500005;constintM=2000005;inlinevoidsolve(){intn;cin>>n;vector<int>num(n+1),sum(n+1);for(inti=1;i<=n;i++)cin>>num[i];for(inti=1;i<=n;i++)sum[i]=sum[i-1]^num[i];intxor1=0,xor0=0;string s;cin>>s;for(inti=0;i<n;i++){if(s[i]=='1'){xor1^=num[i+1];}else{xor0^=num[i+1];}}intq;cin>>q;while(q--){intid;cin>>id;if(id==1){intl,r;cin>>l>>r;xor0^=sum[r]^sum[l-1];xor1^=sum[r]^sum[l-1];}else{intx;cin>>x;if(x==0){cout<<xor0<<" ";}else{cout<<xor1<<" ";}}}cout<<endl;}signedmain(){ios;intT=1;cin>>T;for(;T--;)solve();return0;}
