codeforces 282E Sausage Maximization

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

题意：给出一个数列A，选择A的一个前缀s1和一个后缀s2，使得s1的抑或值和s2的抑或值的抑或值最大？

思路：将前缀依次插入trie中，对于插入的每个前缀i，在trie中查找与后缀i+1抑或值的最大值。

int trie[N*80][2],e;
i64 a[N],b[N],c[N],ans,tot,val[N*80];
int n;

void insert(i64 x)
{
    int p=0,i;
    for(i=42;i>=0;i--)
    {
        if(!trie[p][x>>i&1]) trie[p][x>>i&1]=++e;
        p=trie[p][x>>i&1];
    }
    val[p]=x;
}

i64 query(i64 x)
{
    int p=0,i;
    for(i=42;i>=0;i--)
    {
        if(x&(1ll<<i))
        {
            if(trie[p][0]) p=trie[p][0];
            else p=trie[p][1];
        }
        else
        {
            if(trie[p][1]) p=trie[p][1];
            else p=trie[p][0];
        }
    }
    return val[p];
}

int main()
{
    RD(n);
    int i;
    FOR1(i,n) RD(a[i]);
    for(i=1;i<=n+1;i++) b[i]=b[i-1]^a[i];
    for(i=n;i>=0;i--) c[i]=c[i+1]^a[i];
    i64 ans=0,temp;
    for(i=0;i<=n;i++)
    {
        insert(b[i]);
        temp=c[i+1]^query(c[i+1]);
        if(temp>ans) ans=temp;
    }
    PR(ans);
    return 0;
}