题目描述
原题来自：CODECHEF September Challenge 2015 REBXOR
1
≤r1<l2≤r2≤N，x⨁yx\bigoplus yx⨁y 表示 xxx 和 yyy 的按位异或。
输入格式
输出格式
输出一行包含给定表达式可能的最大值。
样例
数据范围与提示
5,0≤Ai≤109。
题解
首先记录异或前缀和$s[i]=a[1]⊕a[2]⊕a[3] ...⊕a[i]$。
设$l[i]$为以$i$结尾的区间中，异或值的最大值。
因为异或有 $x⊕x=0$ 的性质，所以区间 $[l,r]$ 的异或值
$=a[l]⊕a[l+1]⊕...⊕a[r]$
$=(a[1]⊕a[2]⊕a[3]...⊕a[l-1])⊕(a[1]⊕a[2]⊕a[3] ...⊕a[r])$
$=s[l-1]⊕s[r]$，
所以求$l[i]$，转化为找$j<i$，使得$s[j]⊕s[i]$最大。
转化为「LOJ#10050」「一本通 2.3 例 2」The XOR Largest Pair（Trie
以相似的方法可以求出$r[i]$（以$i$开头的区间中，异或值的最大值）。
在实际操作的过程中可以$l[i]=max(l[i-1],find(x))$，这样$ans=max(l[i]+r[i+1])$就行了。
书上的操作是直接$l[i]=find(x)$然后$ans=max(l[i]+r[i+1])$，感觉不能理解qwq
编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
# #. 「一本通 2.3 例 」Nikitosh 和异或 Accepted ms KiB C++ / 1.2 K qwerta -- :: #include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int s[];
int l[];
int r[];
struct emm{
int nxt[];
}a[];
int cnt=;
int b[];
void add(int x)
{
int j=-;
memset(b,,sizeof(b));
while(x)
{
b[++j]=x&;
x>>=;
}
int k=;
for(int j=;j>=;--j)
{
if(!a[k].nxt[b[j]])
a[k].nxt[b[j]]=++cnt;
k=a[k].nxt[b[j]];
}
return;
}
int find(int x)
{
int now=,k=;
for(int j=;j>=;--j)
{
if(a[k].nxt[-b[j]])
{
now+=(<<j);
k=a[k].nxt[-b[j]];
}
else k=a[k].nxt[b[j]];
}
return now;
}
int main()
{
//freopen("a.in","r",stdin);
int n;
scanf("%d",&n);
for(int i=;i<=n;++i)
scanf("%d",&s[i]);
int x=;
for(int i=;i<=n;++i)
{
x^=s[i];//这里的x为前缀和
add(x);
l[i]=max(l[i-],find(x));
}
//重做一次找r[i]
memset(a,,cnt+);
x=,cnt=;
for(int i=n;i;--i)
{
x^=s[i];
add(x);
r[i]=max(r[i+],find(x));
}
int ans=;
for(int i=;i<n;++i)
ans=max(ans,l[i]+r[i+]);
cout<<ans;
return ;
}