专题题解 - TEST_34

Solution by uwagjaynoi

题意：

维护数列，支持区间异或，求区间中所有子序列的异或和异或 $v$ 的最小值。

---

我们给出一种不借助差分的本题解法。

用线段树维护区间线性基，关键问题就在于如何将线性基全体异或一个数 $x$。

考虑原先的一个子集 $S$，其异或和为 $X$，那么全体异或 $x$ 后，如果 $2\mid |S|$ 则异或和仍然为 $X$，否则为 $X\oplus x$。因此，我们实际上要用一种方法来刻画子集的奇偶性。

设原先的集合为 $\langle a_1,a_2,\ldots,a_n\rangle$，现在我们将每个数前面加一个标识位，即选择 $y$ 使得 $2^y>a_i$，然后考虑 $\langle 2^y+a_1,\ldots,2^y+a_n\rangle$，这样在一组异或和中若 $2^y$ 对应的位为 $1$ 则是奇数个数异或，否则为偶数个数异或，那么我们再加上一项 $2^y+x$，就可以使得奇数个数异或就必须额外异或上一个 $x$（为了使得 $2^y$ 位为 $0$），而偶数个数异或就不能异或上这个 $x$（否则 $2^y$ 位就会是 $1$）。

所以对于原本的 $\langle a_1,\ldots,a_n\rangle$，将它首先变为 $\langle 2^y,2^y+a_1,\ldots,2^y+a_n\rangle$，然后在需要全体异或 $x$ 时将线性基上 $2^y$ 位代表元异或上 $x$，表示选择奇数个数时需要额外异或一个 $x$ 即可。

时间复杂度与常规做法相同，暂时没有发现这种做法相比差分做法的明显优越性。

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN=50010;
struct LB {
	int c[32];
	LB () {memset(c,0,sizeof(c));}
	void insert (int x) {
		for (int i=30;i>=0;i--) {
			if (x&(1<<i)) {
				if (c[i]) {x^=c[i];}
				else {c[i]=x;return;}
			}
		}
		return;
	}
	int gtmx (int x) {
		for (int i=30;i>=0;i--) {
			if ((x^c[i])>x) {x^=c[i];}
		}
		return x;
	}
}seg[MAXN*4];
LB merge (LB a,LB b) {
	for (int i=0;i<=30;i++) {
		if (b.c[i]) {a.insert(b.c[i]);}
	}
	return a;
} 
int n,m,op,x,y,z,a[MAXN],b[MAXN],fw[MAXN];
void modify_fw (int x,int v) {
	for (int i=x;i<=n;i+=(i&(-i))) {fw[i]^=v;}
	return;
}
int query_fw (int x) {
	int res=0;
	for (int i=x;i;i-=(i&(-i))) {res^=fw[i];}
	return res;
}
void buildt (int p,int l,int r) {
	if (l==r) {seg[p].insert(b[l]);return;}
	int mid=(l+r)>>1;
	buildt(p<<1,l,mid),buildt((p<<1)|1,mid+1,r);
	seg[p]=merge(seg[p<<1],seg[(p<<1)|1]);
	return;
}
void modify (int p,int l,int r,int pos,int v) {
	if (l==r) {
		b[l]^=v;
		seg[p]=LB();
		seg[p].insert(b[l]);
		return;
	}
	int mid=(l+r)>>1;
	if (pos<=mid) {modify(p<<1,l,mid,pos,v);}
	else {modify((p<<1)|1,mid+1,r,pos,v);}
	seg[p]=merge(seg[p<<1],seg[(p<<1)|1]);
	return;
}
LB query (int p,int l,int r,int xl,int xr) {
	if (xr<l||r<xl) {return LB();}
	if (xl<=l&&r<=xr) {return seg[p];}
	int mid=(l+r)>>1;
	return merge(query(p<<1,l,mid,xl,xr),query((p<<1)|1,mid+1,r,xl,xr));
}
int main () {
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) {
		scanf("%d",&a[i]);
		modify_fw(i,b[i]=(a[i]^a[i-1]));
	}
	buildt(1,1,n);
	for (int i=1;i<=m;i++) {
		scanf("%d%d%d%d",&op,&x,&y,&z);
		if (op==1) {
			modify(1,1,n,x,z);
			if (y<n) {modify(1,1,n,y+1,z);}
			modify_fw(x,z);
			if (y<n) {modify_fw(y+1,z);}
		} else {
			int tmp=query_fw(x);
			LB res=query(1,1,n,x+1,y);
			res.insert(tmp);
			printf("%d\n",res.gtmx(z));
		}
	}
	return 0;
}