Description
Input
输入数据的第一行包含一个整数N，表示数组中的元素个数。 第二行包含N个整数A1,A2,…,AN。
Output
输出一行包含给定表达式可能的最大值。
Sample Input
5
1 2 3 1 2
Sample Output
6
HINT
满足条件的(l1,r1,l2,r2)有：(1,2,3,3)，(1,2,4,5)，(3,3,4,5)。
对于100%的数据，2 ≤ N ≤ 4*105，0 ≤ Ai ≤ 109。
题解
开始写了个可持久化Tire被卡成傻子
我们可以考虑一种算法，枚举割点i，求出1~i的最大xor和与i+1~n的xor和相加记录答案
那么先对于前缀和搞一棵字典树，每次贪心询问记录答案。设当前处理1~i的最大xor和。设cnt表示1~i的xor和，那么可以在1~i-1的区间里找一个值p，满足cnt^p最大。1~i的最大xor和即为1~i-1的最大xor和与cnt^p取max
后缀和同理
注意要处理两条xor和的交界点不能相同
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
inline int read()
{int f=1,x=0;char ch=getchar();while(ch<'0' || ch>'9'){
if(ch=='-')f=-1;ch=getchar();}while(ch>='0' && ch<='9'){
x=x*10+ch-'0';ch=getchar();}return x*f;
}
struct Tire
{int son[2],s;
}tr[18000000];int trlen,root;
int tmp[35],a[35];
void get(int x)
{int ln=0;while(x){a[++ln]=x%2;x/=2;}
// for(int i=1;i<=ln;i++)printf("%d",tmp[i]);memset(tmp,0,sizeof(tmp));for(int i=1;i<=ln;i++)tmp[31-i+1]=a[i];
}
void add()
{int p=root;for(int i=1;i<=31;i++){if(tr[p].son[tmp[i]]==0)tr[p].son[tmp[i]]=++trlen;p=tr[p].son[tmp[i]];tr[p].s++;}
}
int ans[35];
void fdmax()//l~r中找最大xor
{memcpy(ans,tmp,sizeof(ans));int p=root;for(int i=1;i<=31;i++){int lc=tr[p].son[0],rc=tr[p].son[1];if(tmp[i]==1){if(tr[lc].s>0)ans[i]=1,p=lc;else if(tr[rc].s>0)ans[i]=0,p=rc;else return ;}else{if(tr[rc].s>0)ans[i]=1,p=rc;else if(tr[lc].s>0)ans[i]=0,p=lc;else return ;}}
}
int n;int fir[510000],las[510000],us[510000],col[510000];
int main()
{n=read();int cnt=0;root=0;add();for(int i=1;i<=n;i++){col[i]=read();cnt^=col[i];get(cnt);add();fdmax();int ret=0;for(int j=1;j<=31;j++)if(ans[j]==1)ret+=(1<<(31-j));fir[i]=max(fir[i-1],ret);}for(int i=0;i<=trlen;i++)tr[i].son[0]=tr[i].son[1]=0,tr[i].s=0;trlen=0;cnt=0;get(0);add();for(int i=n;i>=1;i--){cnt^=col[i];get(cnt);add();fdmax();int ret=0;for(int j=1;j<=31;j++)if(ans[j]==1)ret+=(1<<(31-j));las[i]=max(las[i+1],ret);}int ret=0;for(int i=0;i<=n;i++)ret=max(ret,fir[i]+las[i+1]);printf("%d\n",ret);return 0;
}