Input

输入数据的第一行包含一个整数N，表示数组中的元素个数。

第二行包含N个整数A1,A2,…,AN。

 

 

 

Output

输出一行包含给定表达式可能的最大值。

 

 

Sample Input

51 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。

 

题解：

其实很好想的，维护一个lmx[i]表示到1-i中最大的连续的xor和。

rmx[i]表示i-n重最大的连续的xor和，然后就是前缀和的形式

插入字典树，然后在字典树中找两个值的xor最大值。

就是找1的时候向0的方向找，0的时候向1的方向找。

很好理解吧。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #define N 400007 7 using namespace std; 8  9 int n,cnt=1;10 int a[N],lmx[N],rmx[N];11 struct Node12 {13     int point[2];14     void init()15     {16         point[1]=point[0]=0;17     }18 }trie[400007*30];19 20 void insert(int x)21 {22     int now=1;23     for (int i=31,t;i>=0;i--)24     {25         if (x&(1<
           
            =0;i--)35 {36 if (x&(1<
            
             =1;i--)65 {66 x=x^a[i];67 insert(x);68 rmx[i]=max(rmx[i+1],calc(x));69 }70 int ans=-1;71 for (int i=2;i<=n;i++)72 ans=max(ans,lmx[i-1]+rmx[i]);73 printf("%d\n",ans); 74 }