[CF282E]Sausage Maximization

282E:Sausage Maximization

题意简述

给出长度为$n$的数列。
选择出这个数列的一个前缀，和一个后缀是的它们的异或和最大。

数据范围

$1 \leq n \leq 10^5$
$1 \leq a_i \leq 10^{12}$

思路

异或是自身的逆运算。
我们可以把这个数列变成前缀和。
一个前缀异或一个后缀，可以转化为：所有的异或和异或一个区间。
利用Trie树维护。
每次插入一个前缀和，并查询它前面的所有前缀与他形成的最大值。

代码

#include<cstdio>
#include<iostream>
using namespace std;
namespace Trie
{
    struct Node{
        Node *ch[2];
        Node();
    }*null;
    Node::Node()
    {
        ch[0]=ch[1]=null;
    }
    Node pool[4100010];
    Node *Root;
    int poolt;
    Node *NewNode()
    {
        pool[poolt]=Node();
        return &pool[poolt++];
    }
    void Init()
    {
        null=NewNode();
        *null=Node();
        Root=NewNode();
    }
    void insert(long long val)
    {
        Node *r=Root;
        for (int i=40;i>=0;i--)
        {
            bool x=bool(val&(1LL<<i));
            if (r->ch[x]==null)
                r->ch[x]=NewNode();
            r=r->ch[x];
        }
    }
    long long query(long long val)
    {
        Node *r=Root;
        long long ret=0;
        for (int i=40;i>=0;i--)
        {
            bool x=bool(val&(1LL<<i));
            if (r->ch[x^1]==null)
                r=r->ch[x];
            else
            {
                r=r->ch[x^1];
                ret+=(1LL<<i);
            }
        }
        return ret;
    }
}
int n;
long long seq[100010],ans;
void init()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        scanf("%I64d",&seq[i]);
    for (int i=1;i<=n;i++)
        seq[i]^=seq[i-1];
    Trie::Init();
}
void work()
{
    Trie::insert(0);
    for (int i=1;i<=n;i++)
    {
        Trie::insert(seq[i]);
        ans=max(ans,Trie::query(seq[i]^seq[n]));
    }
    printf("%I64d",ans);
}
int main()
{
    init();
    work();
    return 0;
}