bzoj 4260 Codechef REBXOR

Description

Input

输入数据的第一行包含一个整数N，表示数组中的元素个数。
第二行包含N个整数A1,A2,…,AN。

Output

输出一行包含给定表达式可能的最大值。

Sample Input

5

1 2 3 1 2

Sample Output

6

HINT

满足条件的(l1,r1,l2,r2)有：(1,2,3,3)，(1,2,4,5)，(3,3,4,5)。

对于100%的数据，2 ≤ N ≤ 4*105，0 ≤ Ai ≤ 109。

题解

对于这种形式求最大值的，那肯定是求一个前缀最大和后缀最大，再枚举下断点。

那就很显然了，用Trie树搞下就可以了。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 500010
using namespace std;
int inline read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int ch[N*30][2],a[N],l[N],r[N],n,root=1,sz=1,ans;
void add(int x)
{
    for (int i=30,now=root;i>=0;now=ch[now][(x&(1<<i))>>i],i--)
        if (!ch[now][(x&(1<<i))>>i])
            ch[now][(x&(1<<i))>>i]=++sz;
}
int query(int x)
{
    int ans=0;
    for (int i=30,now=root;i>=0;i--)
        if (ch[now][((x&(1<<i))>>i)^1])
            now=ch[now][((x&(1<<i))>>i)^1],ans+=(1<<i);
        else if (ch[now][(x&(1<<i))>>i])
            now=ch[now][(x&(1<<i))>>i];
        else break;
    return ans;
}
main()
{
    n=read();
    for (int i=1;i<=n;i++)
        a[i]=read();
    add(0);
    for (int i=1,now=0;i<=n;i++)
        now^=a[i],l[i]=max(l[i-1],query(now)),add(now);
    memset(ch,0,sizeof 0),add(0);
    for (int i=n,now=0;i>=0;i--)
        now^=a[i],r[i]=max(r[i+1],query(now)),add(now);
    for (int i=1;i<n;i++)
        ans=max(ans,l[i]+r[i+1]);
    printf("%d\n",ans);
}