思路
一眼顶真，这不就是线段树吗？还挺板的，然后速打了一个线段树。
就是用两个变量分别存这个区间的两个异或值，修改就是交换这两个变量的值，询问都是询问整体的，应该很好写，就不细讲了。
AC code
#include<bits/stdc++.h>
using namespace std;
struct node{long long l,r,xor0,xor1,tag;}t[400005];
long long T,n,v[100005],m,op,a,b;
char s[100005];
inline void pushup(long long p){t[p].xor0=t[p<<1].xor0^t[p<<1|1].xor0,t[p].xor1=t[p<<1].xor1^t[p<<1|1].xor1;}
inline void pushdown(long long p){swap(t[p<<1].xor0,t[p<<1].xor1),t[p<<1].tag^=1,swap(t[p<<1|1].xor0,t[p<<1|1].xor1),t[p<<1|1].tag^=1,t[p].tag=0;}
void build(long long p,long long l,long long r)
{
t[p].l=l,t[p].r=r,t[p].tag=0;
if(l==r)
{
if(s[l]=='0') t[p].xor0=v[l],t[p].xor1=0;
else t[p].xor0=0,t[p].xor1=v[l];
return;
}
long long mid=l+r>>1;
build(p<<1,l,mid),build(p<<1|1,mid+1,r);
pushup(p);
}
void update(long long p,long long l,long long r)
{
if(t[p].l>=l&&t[p].r<=r){swap(t[p].xor0,t[p].xor1),t[p].tag^=1;return;}
if(t[p].tag) pushdown(p);
long long mid=t[p].l+t[p].r>>1;
if(mid>=l) update(p<<1,l,r);
if(mid<r) update(p<<1|1,l,r);
pushup(p);
}
long long ask(long long p,long long l,long long r,long long k)
{
if(t[p].l>=l&&t[p].r<=r) return (k)?t[p].xor1:t[p].xor0;
if(t[p].tag) pushdown(p);
long long mid=t[p].l+t[p].r>>1,ans=0;
if(mid>=l) ans=ask(p<<1,l,r,k);
if(mid<r) ans=ans^ask(p<<1|1,l,r,k);
return ans;
}
int main()
{
scanf("%lld",&T);
while(T--)
{
scanf("%lld",&n);
for(int i=1;i<=n;++i) scanf("%lld",&v[i]);
scanf("%s%lld",s+1,&m),build(1,1,n);
while(m--)
{
scanf("%lld%lld",&op,&a);
if(op==1) scanf("%lld",&b),update(1,a,b);
else printf("%lld ",ask(1,1,n,a));
}
puts("");
}
}
另一种做法
一起打 CF 的另一个老哥没有用线段树，而是用了异或的性质。
因为一个数异或自己一定是 \(0\)，那么区间修改，就等于是异或这个区间原来有的数，把原来有的通过异或除掉，再异或原来没有的数，让他出现。
假设用两个变量 \(s0\) 和 \(s1\) 分别存整个区间的两个异或和，那么修改一个区间就是把这个区间的异或和异或给 \(s0\) 和 \(s1\)。
可以提前预处理出异或前缀和，然后按照要求操作就行了。
因为没写这个方法，我又太懒了，所以这里就不放代码了。