【练习】CodeForces282E Sausage Maximization （01字典树）

题意

翻译过来题意大致如下：
给定一个长度为$n$的序列，请找出一个不相交的前缀和后缀，并且这个前缀和后缀异或值最大。输出这个最大值。
注意前缀和后缀可能为空（也就是都为0）。

题解

首先一看数据范围，就知道要开long long，如果暴力寻找，复杂度肯定是说不过去的。求解异或问题可以考虑01字典树。
我们可以枚举每一个后缀，考虑这个能与这个后缀异或的到最大值的前缀。对于这个后缀的每一位，若他为1，为了保证最后异或和最大，最好为0，反之最好为1。这样我们就可以在前缀组成的01字典树中去寻找这个最大前缀了。
时间复杂度$O(64*n)$

代码

#include<bits/stdc++.h>
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const int nmax = 1e5+7;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const ull p = 67;
const ull MOD = 1610612741;
ll prefix[nmax],suffix[nmax],a[nmax];
int n;
struct Tire{
    int cnt = 0;
    int node[nmax*50][2];
    void insert(ll val){
        int now = 0,nxt = 0;
        for(int i = 63;i>=0;--i){
            nxt = (val & (1LL<<i))>0;
            if(!node[now][nxt]) node[now][nxt] = ++cnt;
            now = node[now][nxt];
        }
    }
    ll query(ll val){
        ll ans = 0; int now = 0, pos = 0;
        for(int i = 63;i>=0;--i){
            pos = (val & (1LL<<i))>0;
            if(node[now][pos^1]) now = node[now][pos^1], pos = pos ^ 1;
            else  now = node[now][pos];
            ans += (1LL * (pos))<<i;
        }
        return ans;
    }
    void clear(){cnt = 0; memset(node,0,sizeof node);}
}t;
int main(){
    scanf("%d",&n);
    for(int i = 1;i<=n;++i) scanf("%I64d",&a[i]),prefix[i] = prefix[i-1] ^ a[i];
    for(int i = n;i>=1;--i) suffix[i] = suffix[i+1] ^ a[i];
    t.clear();
    ll ans = 0,temp;
    for(int i = 0;i<=n+1;++i){
        t.insert(prefix[i]);
        temp = t.query(suffix[i+1]);
        ans = max(ans,temp^suffix[i+1]);
    }
    printf("%I64d",ans);
    return 0;
}