[BZOJ4260] Codechef REBXOR (01字典树,异或前缀和)

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。

Source

By yts1999

Solution

考虑几点:

• 我们所选的区间不能相交。
• 显而易见的贪心,我们所选的区间必须是区域内异或和最大的。

于是我们考虑用 01字典树 来求解。
我们可以很方便地处理出在一段区间内最大异或和的区间。
直接记录一遍异或前缀和,然后一个一个插入并查询即可。
但是由于不能选相交的区间,我们不能考虑直接选两个最大的区间。

可以考虑用一个数组:
[f[maxn]]
用于储存前 ((1 , i )) 区间的异或最大值。
那么我们记录完之后,直接从后面再开始一遍选最大区间。
我们从 (n) 枚举到 (1);
[Ans=max_{i=1}^n(Ans,f[i-1]+query(sub[i]))]
其中 (sub) 数组表示 (n) 到 (i) 异或后缀和。
如以上求解即可,时间复杂度 (O(2*nlogn))。
不过这题需要注意以下空间不能开太大。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=400008;
int c[maxn],f[maxn];
int n,m,pre[maxn],sub[maxn];
int ch[32*maxn][2];
int val[32*maxn];
int num[32*maxn];
int sz,ans=-1;
void init()
{
    memset(ch[0],0,sizeof(ch[0]));
    sz=1;
}
void insert(int a)
{
    int u=0;
    for(int i=32;i>=0;i--)
    {
        int c=((a>>i)&1);
        if(!ch[u][c])
        {
            memset(ch[sz],0,sizeof(ch[sz]));
            val[sz]=0;
            num[sz]=0;
            ch[u][c]=sz++;
        }
        u=ch[u][c];
        num[u]++;
    }
    val[u]=a;
    return;
}

int query(int x)
{
    int u=0;
    for(int i=32;i>=0;i--)
    {
        int c=((x>>i)&1);
        if(ch[u][c^1]&&num[ch[u][c^1]]) 
        u=ch[u][c^1];
        else u=ch[u][c];
    }
    return x^val[u];
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) 
    scanf("%d",&c[i]);
    for(int i=1;i<=n;i++) 
        pre[i]=pre[i-1]^c[i];
    for(int i=n;i>0;i--) 
        sub[i]=sub[i+1]^c[i];
    
    for(int i=1;i<=n;i++)
        f[i]=max(f[i-1],query(pre[i])), 
            insert(pre[i]);
    init(); insert(sub[n+1]);
    
    for(int i=n;i>0;i--)
        ans=max(ans,query(sub[i])+f[i-1]),
            insert(sub[i]);
    cout<<ans<<endl;
    return 0;
}