点击打开链接
题意:给出n个数,n<=4e5 求出两个连续不相交区间使得( [a[l1]..xor ..a[r1]]) + (a[l2] xor a[l2+1] ...xor a[r2])最大 如果先把前缀1..i-1的异或值都插入到Trie中 此时在Trie中查询到与前缀i异或的最大值,即以i结尾最大异或区间. 利用dp记录前i个数的最大异或值,枚举第二段区间开头i时,查询后缀i的最大异或值+dp[i-1]即可得到ans
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=4e5+20; int n,a[N]; int pre[N],suf[N],dp[N]; int sz,ch[32*N][2],v[32*N]; void init() { memset(ch[0],0,sizeof(ch[0])); memset(v,0,sizeof(v)); sz=1; } void insert(int x) { int u=0; for(int i=31;i>=0;i--) { int c=(x>>i)&1; if(!ch[u][c]) { memset(ch[sz],0,sizeof(ch[sz])); ch[u][c]=sz++; } u=ch[u][c]; } v[u]=x; } int query(int x) { int u=0; for(int i=31;i>=0;i--) { int c=(x>>i)&1; if(ch[u][c^1]) u=ch[u][c^1]; else u=ch[u][c]; } return x^v[u]; } int main() { while(cin>>n) { init(); insert(0); memset(dp,0,sizeof(dp)); pre[0]=suf[n+1]=0; for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) pre[i]=pre[i-1]^a[i]; for(int i=n;i>=1;i--) suf[i]=suf[i+1]^a[i]; for(int i=1;i<=n;i++) { dp[i]=max(dp[i-1],query(pre[i])); insert(pre[i]); } init(); insert(0); int ans=0; for(int i=n;i>=1;i--) { ans=max(ans,dp[i-1]+query(suf[i])); insert(suf[i]); } cout<<ans<<endl; } return 0; }