返回首页 返回专题

【BZOJ4260】REBXOR 题解

首先，我们知道异或有一个良好的性质：a^b^a=b（这里的符号^以及后文中的^都表示异或），这允许了我们使用前缀和的思想处理连续异或和

所以a[l]^a[l+1]^a[l+2]^…^a[r]=sum[r]^sum[l-1]，其中sum表示前缀异或和

因此，我们如果在计算第i位之前将sum[1…i-1]建成了Trie树，就可以得到i与前面连续一段的最大异或和（具体方法参考字典树的妙用），计算完再把sum[i]插入Trie树，继续计算下一位

对于这题而言，我们正着、倒着分别做一遍，把每一位的计算结果存进lx、rx两个数组中，然后用前缀max的方法处理lx，用后缀max的方法处理rx，然后枚举每一个分界点，则ans={分界点左侧的lx+右侧的rx}

细节参考代码

#include<bits/stdc++.h>
using namespace std;

const int N=400100;
struct Node{int ch[2];} nd[N*31];
int sz;
int a[N],n;
int lx[N],rx[N];

void insert(int x)
{
	int now=0;
	for(int i=30;i>=0;i--)
	{
		int j=(x>>i)&1;
		if(!nd[now].ch[j])nd[now].ch[j]=++sz;
		now=nd[now].ch[j];
	}
}

int query(int x)
{
	int ans=0,now=0;
	for(int i=30;i>=0;i--)
	{
		int j=((x>>i)&1)^1;
		if(nd[now].ch[j]) ans|=(1<<i);
		else j^=1;
		now=nd[now].ch[j];
	}
	return ans;
}

int main()
{
	scanf("%d",&n);n++;
	for(int i=2;i<=n;i++) scanf("%d",a+i);
	int sum=0;
	insert(0);
	lx[1]=0;
	for(int i=2;i<=n;i++)
	{
		sum^=a[i];
		insert(sum);
		lx[i]=query(sum);
		lx[i]=max(lx[i],lx[i-1]);
	}
	sz=0;sum=0;
	memset(nd,0,sizeof(nd));
	insert(0);
	for(int i=2;i<=n/2+1;i++) swap(a[i],a[n-i+2]);
	rx[1]=0;
	for(int i=2;i<=n;i++)
	{
		sum^=a[i];
		insert(sum);
		rx[i]=query(sum);
		rx[i]=max(rx[i],rx[i-1]);
	}
	for(int i=2;i<=n/2+1;i++) swap(rx[i],rx[n-i+2]);
	int ans=0;
	for(int i=2;i<n;i++) ans=max(ans,lx[i]+rx[i]);
	cout<<ans<<endl;
	return 0;
}