Codefoces 282E - Sausage Maximization

http://codeforces.com/problemset/problem/282/E
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 ≤ 105).

The next line contains n integers a1, a2, ..., an (0 ≤ ai ≤ 1012) — 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

Copy

2
1 2

output

Copy

3

input

Copy

3
1 2 3

output

Copy

3

input

Copy

2
1000 1000

output

Copy

1000

https://blog.csdn.net/mengxiang000000/article/details/74149135
给一个长度为n的整数序列，现在要你截取这个序列的一个前缀和一个后缀(前缀和后缀不能相交)，使得前缀和后缀的异或值最大。

思路：
贪心去做，对于每个查询，同样处理成35位二进制01字符串，对应进行查询，如果当前位子是0，那么尽量往1那边走，同理，如果当前位子是1，那么尽量往0那边走即可。

那么O（n）建树+查询即可。

https://gist.github.com/phonism/6604961
https://blog.csdn.net/DOLFAMINGO/article/details/73867435
1.预处理前缀异或、后缀异或。

2.枚举每一个前缀异或（i：0~n）：

2.1.将此前缀异或加入到Trie树中，

2.2.根据后一位的后缀异或，在Trie树中查找与之异或后的最大值，并一直更新ans。

学习之处：

当需要在一个序列的中间删除若干个连续元素，使得满足xx条件时：

1.预处理出前缀和、后缀和。

2.枚举每一个前缀和：将此前缀和插入某种数据结构中，再用后一位的后缀和在此数据结构中查找。

类似的题目：http://blog.csdn.net/dolfamingo/article/details/71001021

typedef struct node
{
    struct node *next[2];
}Node, *Trie;

Trie T;
LL n, a[maxn], pre[maxn], rev[maxn];

void init()
{
    scanf("%I64d",&n);
    for(int i = 1; i<=n; i++)
        scanf("%I64d",&a[i]);
    for(int i = 1; i<=n; i++)   //前缀
        pre[i] = pre[i-1]^a[i];
    for(int i = n; i>=1; i--)   //后缀
        rev[i] = rev[i+1]^a[i];

    T = new Node;   //初始化Trie树
    T->next[0] = T->next[1] = NULL;
}

void add(LL x)
{
    Trie p = T;
    for(int i = 50; i>=0; i--)  //从高位到低位
    {
        int d = (x>>i)&1;
        if(p->next[d]==NULL)    //此位的d不存在， 则新建
            p->next[d] = new Node, p->next[d]->next[0] = p->next[d]->next[1] = NULL;
        p = p->next[d];
    }
}

LL query(LL x)
{
    LL tmp = 0;
    Trie p = T;
    for(int i = 50; i>=0; i--)
    {
        //如果!d路存在，则可加上（d ^ !d = 1）, 并顺着这条路走下去； 否则走d路（!d路和d路至少一路存在）
        int d = (x>>i)&1;
        if(p->next[!d]) tmp += 1LL*(1LL<<i), p = p->next[!d];
        else p = p->next[d];
    }
    return tmp;
}

void solve()
{
    LL ans = 0;
    for(int i = 0; i<=n; i++) //i为0时， 没有前缀；i为n时，没有后缀。
    {
        add(pre[i]);
        ans = max( ans, query(rev[i+1]) );
    }
    printf("%I64d\n",ans);
}

int main()
{
    init();
    solve();
}

http://www.voidcn.com/article/p-pytyhqxq-wu.html

思路：对于一个后缀，将他前面的所有的前缀加到一个Trie树中，然后根据这个后缀数每个位上的0和1，寻找使其异或最大的数。

http://www.cnblogs.com/zhj5chengfeng/archive/2013/05/14/3077621.html

如果这种题目没见过类似的话，感觉挺神的，一个长度为 10⁵ 的数组，怎么去选前缀和后缀？不过不要惊慌，题目出出来是给我们做的，总有一线生机！

先从最暴力的开始讲起：枚举每一个后缀，让他和所有不与之相交的前缀求异或值，那么转化成了：

       给一个数 a，还有一堆数，怎么在这一堆数中找出一个数 b，a 和 b 的异或值最大？

想想：肯定要先把 a 和这一堆数转化成二进制数，枚举 a 的最高位，要使异或值最大，那么 b 从最高位开始，就要尽量与 a 对应的位不同，对不对？

想到这里，那就好办了：把这一堆数装进一个字典树中，当然，是从最高位开始装，然后就是在这一棵字典树中尽量找出与 a 当前位不同的数，直到找到最低位为止，那么当前路径上经过的数就是我们的数 b 了，a 异或 b 也一定是最大的

上面的问题解决了，这道题也就迎刃而解了：先把所有的数异或起来，作为最初的后缀，而前缀是 0，先插入字典树中，然后，每次将后缀“减一”，前缀“加一”，先把前缀加入字典树中，再在字典树中查询与当前的后缀异或值最大的数

总的时间复杂度 64*n

http://www.voidcn.com/article/p-piuhwttp-hk.html

struct node
{
       int son[2]; 
       ll w;
}p[10000005];
ll a[100005],totol,ans,_2jie[45];
int num;
void InsertToTrie(ll x)
{
       int h=0,i,t;
       for (i=40;i>=0;i--)
       {
             if (x & _2jie[i]) t=1;
                else t=0;
             if (!p[h].son[t]) p[h].son[t]=++num;
             h=p[h].son[t];
       }       
       p[h].w=x;
       return;
}
ll SerchMax(ll x)
{
       int h,i,t;
       h=0;
       for (i=40;i>=0;i--)
       {
             if (x & _2jie[i]) t=1;
                else t=0;
             if (p[h].son[1-t]) h=p[h].son[1-t];
                else h=p[h].son[t]; 
       }
       return p[h].w;
} 
int main()
{
       int i,n;
       ll prefix,postfix; 
       _2jie[0]=1;
       for (i=1;i<=40;i++) _2jie[i]=_2jie[i-1]*2;
       while (~scanf("%d",&n))
       {
             postfix=0;
             for (i=1;i<=n;i++) scanf("%I64d",&a[i]),postfix^=a[i]; 
             memset(p,0,sizeof(p));
             ans=postfix;
             num=0;
             prefix=0;
             InsertToTrie(0);
             for (i=1;i<=n;i++)
             {
                    prefix^=a[i];
                    InsertToTrie(prefix);
                    postfix^=a[i]; 
                    ans=max(ans,SerchMax(postfix)^postfix);
             }
             printf("%I64d\n",ans);    
       }
       return 0;
}