前置知识：异或定义

这里不再进行严格定义，严格定义需要借助抽象代数中格的定义。会的都会，不会的自己去看就行。

我们直观地可以用以下方法定义。

真值表

0	0	0
0	1	1
1	0	1
1	1	0

当A与B相等时，为0，不等时为1。

代数

定义与、或、非运算 （与应该叫做合取，或应该叫析取，这里为了方便就这么说了）

0	0	0
0	1	0
1	0	0
1	1	1

为了方便，这里将 简记为 。

0	0	0
0	1	1
1	0	1
1	1	1

0	1
1	0

那么 =。

两个定义是完全等价的。

由于布尔代数仅考虑集合 ，并不适用于整数集 ，因此我们对定义进行平凡的推广。

按位异或为每一位分别异或。比如

= ==

按位异或在C++中使用 ^ 表示，比如 c=a^b。

异或具有一些性质，下面的性质可以直观理解，这里简单地证明一下。

异或满足结合律

有两种办法可以证明。一种是代数推式子，一种是真值表。 满足结合律也就是证明 =。它的证明是很简单的，不妨自行证明一下。

异或满足交换律

由真值表可以很容易看出。

异或存在幺元

如果存在元素 ，使得==，那么元素 是幺元，也叫单位元。

由定义可知，=，因此 是异或的幺元。

任意元素在异或运算下存在唯一逆元，且逆元为自身

如果存在元素，使得==，那么 为 的逆元，记为。

由定义可知，=，因此任何元素自身是它自己的一个逆元。

假设存在其它逆元，即 =，那么 =====。因此只有一个。

上述证明方法是抽象代数常见的证明方法。

由于逆元为自己，所以如果要“减去”一些异或，就等于异或上它们。

维护前缀异或和

定义数组前缀异或和 =。

那么由性质可知，=。

对于某个连续区间的异或和，==。

好想的 线段树解法

考虑到数据规模只有 ，显然 做法可以通过。

考虑异或的性质，我们可以只维护 为1的元素的异或和。因为所有数的异或和异或上 为1的元素的异或和就是 为0的元素的异或和。

我们可以维护一个线段树，用这个线段树维护区间内 的元素的异或和。这是很容易想到的。也很容易实现。

#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdlib>
#define int long long

using namespace std;

int n,q,a[100005],pre[100005];
char s[100005];

struct SegmentTree
{
	int rt[400005],lazy[400005];
	void build(int x = 1,int l = 1,int r = n)
	{
		if(l==r)
		{
			if(s[l]=='1')rt[x]=a[l];
			else rt[x]=0;
			return;
		}
		int mid = (l+r)/2;
		build(x*2,l,mid);
		build(x*2+1,mid+1,r);
		rt[x]=rt[x*2]^rt[x*2+1];
	}
	void pushdown(int x,int l,int r)
	{
		if(lazy[x])
		{
			int mid = (l+r)/2;
			rt[x*2]=pre[mid]^pre[l-1]^rt[x*2];
			rt[x*2+1]=pre[r]^pre[mid]^rt[x*2+1];
			lazy[x]=0;
			lazy[x*2]^=1;
			lazy[x*2+1]^=1;
		}
	}
	void merge(int ql, int qr, int x = 1,int l = 1,int r = n)
	{
//		cout<<"ql qr x l r:"<<ql<<' '<<qr<<' '<<x<<' '<<l<<' '<<r<<endl;
		if(ql<=l&&r<=qr)
		{
			rt[x]=pre[r]^pre[l-1]^rt[x];
			lazy[x]^=1;
			return;
		}
		pushdown(x,l,r);
		int mid = (l+r)/2;
		if(ql<=mid)merge(ql,qr,x*2,l,mid);
		if(mid<qr)merge(ql,qr,x*2+1,mid+1,r);
		rt[x]=rt[x*2]^rt[x*2+1];
	}
	int query(int ql,int qr,int x = 1,int l = 1,int r = n)//其实不用写，因为它只查所有元素
	{
		if(ql<=l&&r<=qr)return rt[x];
		pushdown(x,l,r);
		int mid = (l+r)/2;
		int ans = 0;
		if(ql<=mid)ans^=query(ql,qr,x*2,l,mid);
		if(mid<qr)ans^=query(ql,qr,x*2+1,mid+1,r);
		return ans;
	}
}t;

void solve()
{
	cin>>n;
	for(int i = 1;i <= n * 4;i++)t.rt[i]=t.lazy[i]=0;
	for(int i = 1;i <= n;i ++)cin>>a[i],pre[i]=pre[i-1]^a[i];
	cin>>s+1;
	t.build();
	cin>>q;
	while(q--)
	{
		int opt;
		cin>>opt;
		if(opt == 1)
		{
			int l,r;
			cin>>l>>r;
			t.merge(l,r);
		}
		else
		{
			int g;
			cin>>g;
			if(g)cout<<t.query(1,n)<<' ';
			else cout<<(pre[n]^t.query(1,n))<<' ';
		}
	}
	cout<<endl;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	int t;
	cin>>t;
	while(t--)solve();
	return 0;
}

最优的 解法

然而这题实际上可以做到 的时间复杂度。 考虑这样一个情况。

此时答案为

如果对这个序列进行操作 ，那么会变成

此时答案为为

1变0的要删去，0变1的要加上，根据性质，不管是增还是删，都只需要异或即可。而不是0就是1，所以每一个数都相当于异或了一下。

显然，每次修改相当于答案异或上整个区间的异或和。

由异或性质=可知，对于异或前缀和 ，区间上的异或和为 。

那么做法就显而易见了，预处理出来异或前缀和 和初始状态下所有 为1的数的异或和 ，当为操作 时，令 ans^=pre[r]^pre[l-1]，当为操作 时，输出 。

#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdlib>

using namespace std;

int n,q,pre[100005],ans;

void solve()
{
	ans=0;
	cin>>n;
	for(int i = 1;i <= n;i ++)cin>>pre[i],pre[i]^=pre[i-1];
	for(int i = 1;i <= n;i ++)
	{
		char s;
		cin>>s;
		if(s=='1')ans^=pre[i]^pre[i-1];
	}
	cin>>q;
	while(q--)
	{
		int opt;
		cin>>opt;
		if(opt==1)
		{
			int l,r;
			cin>>l>>r;
			ans^=pre[r]^pre[l-1];
		}
		else
		{
			int g;
			cin>>g;
			if(g)cout<<ans<<' ';
			else cout<<(pre[n]^ans)<<' ';
		}
	}
	cout<<endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	int t;
	cin>>t;
	while(t--)solve();
	return 0;
}