CodeForces 282E Sausage Maximization

题目链接：http://codeforces.com/contest/282/problem/E

题意：给一个长度为n的整数序列，现在要你截取这个序列的一个前缀和一个后缀(前缀和后缀不能相交)，使得前缀和后缀的异或值最大。前缀和后缀的异或值为前缀序列中的数和后缀序列中的数，异或的结果，比如，某个序列的前缀为1、 2、 4 ，后缀为8、 16，那么它们的异或值为31.
前缀和后缀可以为空，为空时他们的值为0。

思路：首先这n个数的异或结果是一个定值K，那么问题变成了从这n个数中选取一段连续的区间，其异或结果为X，使得X xor K 最大。
因为前缀和后缀都可以为空，所以选取的一段连续区间之前作为前缀，之后作为后缀。
我们已知K值，要想让X xor K 最大，选取的时候从高位开始，尽量让他们在二进制表示下的每一位相异。
理想状态下，X可以为Y，Y的每个二进制位都是和K相异，这样X xor K就可以达到最大值，但是有可能不存在这种情况，我们就从二进制的最高位开始尽量让X接近于Y。
我们可以建一棵trie树，将f[i]放进去(f[i] = a[1]^a[2]^...^a[i]),那么f[i]^f[j] = a[i+1]^a[i+2]^...^a[j] 可以表示一段区间的异或值。
我们现在来枚举X区间的结尾，每次用f[i]去匹配一个f[k]，使得f[i]^f[k]的值在高位上优先尽量接近Y，这样相当于选取区间[k+1,i]的异或值作为X，每次在[1,i]区间内匹配出来一个最佳区间后更新答案即可。其实也可以直接去枚举后缀区间，在1到后缀区间之前去匹配出一个前缀区间直接算。

//范围是10的12次方，我们就将每个数固定为40位

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>


using namespace std;
#define LL long long
#define rep(i,j,k) for(int i = j; i <= k; i++ )
#define Rrep(i,j,k) for(int i = j; i >= k; i-- )
#define Clean(x,y) memset(x,y,sizeof(x))

int n;
LL a[100009];
LL temp;
LL ans;

LL p[45];
int aim[45];
int Next[1000000][2];
int len;
void init()
{
    Clean(Next,0);
    len = 0;
}
void insert(LL t)
{
    int now = 0;
    int k;
    Rrep(i,39,0)
    {
        if ( p[i] & t ) k = 1;
        else k = 0;
        if ( !Next[now][k] ) Next[now][k] = ++len;
        now = Next[now][k];
    }
}

LL query(LL t)
{
    int now = 0;
    LL ans = 0;
    int k;
    Rrep(i,39,0)
    {
        if ( p[i] & t ) k = 1;
        else k = 0;
        if ( ( aim[i] && Next[now][1-k] ) || ( !aim[i] && Next[now][k] )  )
        {
            ans+=p[i];
            now = aim[i]==1?Next[now][1-k]:Next[now][k];
        }
        else now = aim[i]==0?Next[now][1-k]:Next[now][k];

    }
    return ans;
}

int main()
{
    p[0] = 1;
    rep(i,1,40) p[i] = p[i-1]<<1;

    while(scanf("%d",&n)==1)
    {
        a[0] = 0;
        ans = 0;
        rep(i,1,n)
        {
            scanf("%I64d",&temp);
            a[i] = temp ^ a[i-1];
        }
        ans = max(ans,a[n]);
        rep(i,0,39)
            if ( a[n] & p[i] ) aim[i] = 0; //计算Y
            else aim[i] = 1;
        init();
        insert(a[0]); 
        rep(i,1,n)
        {
            insert(a[i]);
            ans = max(ans,query(a[i]));
        }
        cout<<ans<<endl;
    }
    return 0;
}