BZOJ-4260: Codechef REBXOR

Description

给定序列{a}，求两个不相交子区间，使得子区间的亦或和的和最大。2 ≤ N ≤ 4*10^5，0 ≤ Ai ≤ 10^9。

要是只选一个子区间的话好做，直接维护亦或前缀，对于每个前缀在trie树上找到最优的解，时间复杂度O(n*loga)。
那么对于两个区间，我们可以枚举两个区间在哪里分开。那么只需要处理每个前后缀选出一个子区间的最大亦或。和只选一个子区间方法相同，只需要记录前后缀最值即可，时间复杂度同上。
别忘了0也是前后缀

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,a[401000],L[401000],R[401000];
inline char nc()
{
    static char buf[100000],*p1,*p2;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2) ? EOF : *p1++;
}
inline void read(int &x)
{
    char ch=nc();
    while(ch<'0'||ch>'9') ch=nc();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=nc();
}
int t[13000000][2];
int tot=1,rot=1;
inline void insert(int x)
{
    int p=rot;
    for(int i=30;~i;--i)
    {
        if(!t[p][(x&(1<<i))?1:0]) t[p][(x&(1<<i))?1:0]=++tot;
        p=t[p][(x&(1<<i))?1:0];
    }
}
inline int query(int x)
{
    int p=rot,re=0;
    for(int i=30;~i;--i)
    {
        if(t[p][(x&(1<<i))?0:1]) re|=1<<i,p=t[p][(x&(1<<i))?0:1];
        else p=t[p][(x&(1<<i))?1:0];
    }
    return re;
}
void clear(int x)
{
    if(!x) return ;
    clear(t[x][0]);
    clear(t[x][1]);
    t[x][0]=t[x][1]=0;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i) read(a[i]);
    insert(0);
    for(int i=1;i<=n;++i)
    {
        L[i]=max(L[i-1],query(a[i]));
        insert(a[i]);
    }
    clear(rot); tot=1; insert(0);
    for(int i=n;i;--i)
    {
        R[i]=max(R[i+1],query(a[i]));
        insert(a[i]);
    }
    int ans=0;
    for(int i=1;i<n;++i) ans=max(ans,L[i]+R[i+1]);
    printf("%d",ans);
    return 0;
}