题目链接
https://www.lydsy.com/JudgeOnline/problem.php?id=4260
题目
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。
解题
求区间异或和最大，我们预处理前缀异或和。然后将前缀插入01字典树中，对于某个前缀 j 如果其查询到的与其异或和最大的值是前缀 i 。那么区间[i + 1，j]就是以j为结尾的区间的最优区间。
设dp[i]表示前i个数的运算的第一部分的最大可能值。
那么，dp[i]=max{dp[i-1]，pre[i]^query(pre[i])}.
同理设d[i]为后面的数运算的第二部分的最大可能值。
那么ans=max{dp[i] + d[i+1]}.
AC代码
#include <bits/stdc++.h>
using namespace std;const int maxn=4e5+7;int ch[32*maxn][2],sz;
int val[32*maxn];void init()
{memset(ch[0],0,sizeof(ch[0]));sz=0;
}
void insert(int x)
{int p=0;for(int i=32;i>=0;i--){int c=(x>>i)&1;if(!ch[p][c]){ch[p][c]=++sz;memset(ch[sz],0,sizeof(ch[sz]));}p=ch[p][c];}val[p]=x;
}
int query(int x)
{int p=0;for(int i=32;i>=0;i--){int c=(x>>i)&1;if(ch[p][c^1]) p=ch[p][c^1];else p=ch[p][c];}return val[p];
}int pre[maxn],suf[maxn],a[maxn];
int dp[maxn];//前i个数的可能最大值
int d[maxn];//i~n的可能最大值
int main()
{int n;while(~scanf("%d",&n)){//建一个前缀01字典树init();pre[0]=0;//前i个数的异或和dp[0]=0;insert(pre[0]);//注意要先插入一个0值，否则dp[1]就不等于pre[1]了for(int i=1;i<=n;i++){scanf("%d",&a[i]);pre[i]=pre[i-1]^a[i];insert(pre[i]);dp[i]=max(dp[i-1],pre[i]^query(pre[i]));}init();//重新建一个后缀01字典树suf[n+1]=0;//后缀异或和d[n+1]=0;insert(suf[n+1]);for(int i=n;i>=1;i--){suf[i]=suf[i+1]^a[i];insert(suf[i]);d[i]=max(d[i+1],suf[i]^query(suf[i]));}int ans=0;for(int i=1;i<n;i++)ans=max(ans,dp[i]+d[i+1]);printf("%d\n",ans);}return 0;
}