Sausage Maximization CodeForces - 282E（异或&01字典树）

The Bitlandians are quite weird people. They have their own problems and their own solutions. They have their own thoughts and their own beliefs, they have their own values and their own merits. They have their own dishes and their own sausages!

In Bitland a sausage is an array of integers! A sausage's deliciousness is equal to the bitwise excluding OR (the xor operation) of all integers in that sausage.

One day, when Mr. Bitkoch (the local cook) was going to close his BitRestaurant, BitHaval and BitAryo, the most famous citizens of Bitland, entered the restaurant and each ordered a sausage.

But Mr. Bitkoch had only one sausage left. So he decided to cut a prefix (several, may be zero, first array elements) of the sausage and give it to BitHaval and a postfix (several, may be zero, last array elements) of the sausage and give it to BitAryo. Note that one or both pieces of the sausage can be empty. Of course, the cut pieces mustn't intersect (no array element can occur in both pieces).

The pleasure of BitHaval and BitAryo is equal to the bitwise XOR of their sausages' deliciousness. An empty sausage's deliciousness equals zero.

Find a way to cut a piece of sausage for BitHaval and BitAryo that maximizes the pleasure of these worthy citizens.

Input

The first line contains an integer n (1 ≤ n ≤ 10⁵).

The next line contains n integers a₁, a₂, ..., a_n (0 ≤ a_i ≤ 10¹²) — Mr. Bitkoch's sausage.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Output

Print a single integer — the maximum pleasure BitHaval and BitAryo can get from the dinner.

Examples

Input

2
1 2

Output

3

Input

3
1 2 3

Output

3

Input

2
1000 1000

Output

1000

题意：给你一列数字，要你求出这列数字的前缀异或值与后缀异或值  异或的最大值，要求前后缀不能相交，前后缀可以为空，即为0。前缀异或值：指前i（0<=i<n）项的所有数异或后的值，后缀异或值同理。

样例2解释：前缀值为0，即前缀为空，后缀值为3，即只取最后一个数字，0^3=3.

思路：将每一项前缀值插入到字典树中，并遍历一遍数组后缀值查找最大的异或值即可。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<stack>
using namespace std;
#define inf 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
typedef long long LL;
const int mod=1e9+7;
const double pi=acos(-1);
const double eps=1e-8;
const int N=1e5+10;
LL a[N],maxn,pre[N],net[N];
int trie[N*51][3],tot;
void sert(LL x)
{
    int root=0;
    for(int i=50;i>=0;i--)
    {
        int id=(x>>i)&1LL;//注意1要类型转换不然会wa
        if(!trie[root][id]) trie[root][id]=++tot;
        root=trie[root][id];
    }
}
LL finf(LL x)
{
    LL ans=0;
    int root=0;
    for(int i=50;i>=0;i--)
    {
        int id=(x>>i)&1LL^1LL;
        if(trie[root][id]) ans+=1LL<<i;//如果存在二进制不同的数字就把答案加起来
        else id^=1LL;
        root=trie[root][id];
    }
    return ans;
}
int main()
{
    maxn=tot=0;
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%I64d",&a[i]);
        pre[i]=pre[i-1]^a[i];
    }
    for(int i=n;i>=1;i--)
        net[i]=net[i+1]^a[i];
    for(int i=1;i<=n+1;i++)
    {
        sert(pre[i-1]);//插入前缀
        maxn=max(maxn,finf(net[i]));//寻找后缀与前缀的异或最大值
    }
    printf("%I64d\n",maxn);
}

没用位运算的代码

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<stack>
using namespace std;
#define inf 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
typedef long long LL;
const int mod=1e9+7;
const double pi=acos(-1);
const double eps=1e-8;
const int N=1e5+10;
LL a[N],maxn,pre[N],net[N];
int trie[N*51][3],tot;
char s[55],ans[55];
void sert(LL x)
{
    int root=0,k=0;
    while(x)
    {
        s[k++]=x%2+'0';
        x/=2;
    }
    for(int i=k;i<51;i++)
        s[k++]='0';
    s[k]='\0';
    for(int i=k-1;i>=0;i--)
    {
        int id=s[i]-'0';
        if(!trie[root][id]) trie[root][id]=++tot;
        root=trie[root][id];
    }
}
LL finf(LL x)
{
    int root=0,k=0,kk=0;
    while(x)
    {
        s[k++]=x%2+'0';
        x/=2;
    }
    for(int i=k;i<51;i++)
        s[i]='0';
    s[51]='\0';
    for(int i=50;i>=0;i--)
    {
        int id=s[i]-'0';
        id=id==1?0:1;
        if(trie[root][id]) ans[kk++]=id+'0';
        else
        {
            id=id==1?0:1;
            ans[kk++]=id+'0';
        }
        root=trie[root][id];
    }
    LL tmp=0,t=1;
    for(int i=50;i>=0;i--)
    {
        tmp+=(ans[i]-'0')*t;
        t*=2;
    }
    return tmp;
}
int main()
{
    maxn=tot=0;
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%I64d",&a[i]);
        pre[i]=pre[i-1]^a[i];
    }
    for(int i=n;i>=1;i--)
        net[i]=net[i+1]^a[i];
    for(int i=1;i<=n+1;i++)
    {
        sert(pre[i-1]);
        maxn=max(maxn,net[i]^finf(net[i]));
    }
    printf("%I64d\n",maxn);
}