题目描述
对于一个长度为 $n$ 的序列 $s$，定义函数
$$f(s)=\max \lbrace (s_1 \ xor \ s_2 \ xor \ \cdots \ xor \ s_i)+(s_{i+1} \ xor \ s_{i+2} \ xor \ \cdots \ xor \ s_{n})|i \in [0, n]\rbrace$$
给定序列 $a$，求 $a$ 每个前缀的 $f$ 值。
思路
令 $s$ 为 $a$ 的前缀 $xor$，我们发现，对于 $a$ 的前缀 $i$ 项，我们要求使得 $s_j+s_j \ xor \ s_i$ 最大的 $j$。
显然，$s_i$ 为 1 的二进制位不影响答案，我们只需要考虑当 $s_i$ 的某一位为 0 时，能否贪心地找到一个 $j$ 使得这一位对答案产生贡献。
我们从高位开始，在 $s_i$ 上选取一些为 0 的位置，添加一个位置的时候判断这些位置都为 1 的 $s_j$ 是否存在。
于是维护一个 $f_i$，表示包含集合 $i$ 的 $j$ 的最小值，每次判断 $f$ 的值是否小于等于 $i$ 即可。
代码
#include
#define min(a,b) (ab?a:b)
#define maxn 500000
int a[maxn],f[maxn<<2],n,mx;
int main(){
scanf("%d",&n);
memset(f,0x3f,sizeof(f));
for(register int i=1;i<=n;++i){
scanf("%d",&a[i]);
a[i]=a[i]^a[i-1];
f[a[i]]=min(f[a[i]],i);
mx=max(mx,a[i]);
}
for (register int i=mx;~i;--i)
for (register int j=19;~j;--j)
if (!(i&(1<