Codeforces Round #173 (Div. 2) E - Sausage Maximization (01字典树)

题意：

给你n个数字，找出一个前缀一个后缀，使得前缀和后缀所有的数异或后最大，前后缀都可以为空但不能有重合部分

思路：

当我处理某个后缀的时候，它符合题意的前缀是已知的，如果我们预处理出前缀和后缀，那么后缀的值我们是知道的，而因为我们要进行的是异或操作，那么从二进制的角度来看，我们是可以贪心地找出这个后缀和哪个前缀异或后值最大。（比如我们假设某个数的二进制是从右到左的，那么我们从左到右去贪心，遇到1那么我们优先找0，反之亦然，然后不断更新值，这样贪心的结果就是异或后最大的）
那么我们就可以，一个个地把前缀放入字典树，然后用后缀去贪心。因为我们的前缀是一个个放入字典树，我们某个后缀符合题意得前缀就不会有疏漏，这样不断更新字典树和ans，就能得到我们的答案了。

错误及反思：

一开始是枚举后缀去删前缀。。。。相当麻烦，所以cnt数组写搓了，各种wa，有时候觉得难度太大就应该重新审视下思路的。。。

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100010;
int tire[maxn*50][2],root,tot,n;
long long arr[maxn],ans=0,pre[maxn],rev[maxn];
int newnode()
{
    memset(tire[tot],-1,sizeof(tire[tot]));
    return tot++;
}
void add(long long x)
{
    int now=root;
    for(int i=50;i>=0;i--)
    {
        long long k=x>>i&1;
        int ne=0;
        if(k) ne=1;
        if(tire[now][ne]==-1)
            tire[now][ne]=newnode();
        now=tire[now][ne];
    }
}
long long Find(long long x)
{
    int now=root;
    long long temp=x;
    for(int i=50;i>=0;i--)
    {
        long long k=(x>>i)&1;
        int ne=0;
        if(k) ne=1;
        if(ne)
        {
            if(tire[now][0]!=-1)
            {
                now=tire[now][0];
            }
            else
            {
                temp-=1ll<<i;
                now=tire[now][1];
            }
        }
        else
        {
            if(tire[now][1]!=-1)
            {
                temp+=(1ll<<i);
                now=tire[now][1];
            }
            else
            {
                now=tire[now][0];
            }
        }
    }
    //printf("%I64d\n",temp);
    return temp;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%I64d",&arr[i]);
    for(int i=1;i<=n;i++)
        pre[i]=pre[i-1]^arr[i];
    for(int i=n;i>=1;i--)
        rev[i]=rev[i+1]^arr[i];

    tot = 0;
    root = newnode();

    for(int i=0;i<=n;i++)
    {
        add(pre[i]);
        ans=max(ans,Find(rev[i+1]));
    }
    printf("%I64d\n",ans);
}