链接： https://www.lydsy.com/JudgeOnline/problem.php?id=4260

题面：

4260: Codechef REBXOR

Time Limit: 10 Sec  Memory Limit: 256 MB

Submit: 2596  Solved: 1142

[][][]

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。

 

 

前缀和+后缀和维护，用dp[i] 代表从1-i区间异或和最大的值

 

实现代码;

#include
      
       using namespace std;#define ll long longconst int M = 4e5+10;int tot;int ch[32*M][2];ll val[32*M],a[M],pre[M],nex[M],dp[M];void init(){    tot = 1;    ch[0][0] = ch[0][1] = 0;}void ins(ll x){    int u = 0;    for(int i = 32;i >= 0;i --){        int v = (x>>i)&1;        if(!ch[u][v]){            ch[tot][0] = ch[tot][1] = 0;            val[tot] = 0;            ch[u][v] = tot++;        }        u = ch[u][v];    }    val[u] = x;}ll query(ll x){    int u = 0;    for(int i = 32;i >= 0;i --){        int v = (x>>i)&1;        if(ch[u][v^1]) u = ch[u][v^1];        else u = ch[u][v];    }    return x^val[u];}int main(){    ios::sync_with_stdio(0);    cin.tie(0); cout.tie(0);    int n;    cin>>n;    init();    for(int i = 1;i <= n;i ++){        cin>>a[i];    }    pre[0] = nex[n+1] = dp[0] = 0;    for(int i = 1;i <= n;i ++)        pre[i] = pre[i-1]^a[i];    for(int i = n;i >= 1;i --)        nex[i] = nex[i+1]^a[i];    ins(pre[0]);    for(int i = 1;i <= n;i ++){        dp[i] = max(dp[i-1],query(pre[i]));        ins(pre[i]);    }    init();    ins(nex[n+1]);    ll ans = 0;    for(int i = n;i >= 1;i --){        ans = max(ans,dp[i-1]+query(nex[i]));        ins(nex[i]);    }    cout<
       
        <