HYSBZ - 4260 Codechef REBXOR（前缀和求区间连续异或和，01字典树）

链接：HYSBZ - 4260 Codechef REBXOR

题意：

其中$2\le N\le 4\ast 10^5$，$0\le A_i\le 10^9$

分析：

由于异或的性质：$a\oplus a=0$，$0\oplus a=a$

所以 连续区间的异或和$a[L]\oplus a[L+1]\oplus \cdots \oplus a[R]$可以用前缀异或和（或后缀）的形式表示。

如前缀异或和：$pre[i]$，表示$xo{r}_{j=1}^{i}a[j]$

那么有 $a[L]\oplus a[L+1]\oplus \cdots \oplus a[R]=pre[R]\oplus pre[L-1]$

其中 $pre[R]=xo{r}_{j=1}^{R}a[j]$ 和 $pre[L-1]=xo{r}_{j=1}^{L-1}a[j]$ 相同的部分（a[1]~a[L-1]）异或得到0，

而剩下的部分（a[L] ~ a[R]）与0异或，还是本身。

对于该题，要求两段不相交的异或区间和相加的最大结果，可以先处理左边的一段，我们要求得这样一个数组$dp[i]$：表示开头到$i$为止（即$1$ ~ $i$）的最大区间异或和。

我们要先求得$pre\_ans[i]$：表示以$i$结尾（$i$为右端点$R$）的最大区间异或和，求解很简单，根据开始说的区间异或和求法，我们只需要每次在01字典树中找到与$pre[i]$异或的最大值，即为$pre\_ans[i]$，然后把$pre[i]$放入字典树即可。

那么就有$dp[i]=\max (dp[i-1],pre\_ans[i])$

然后再求右边一段，同理从后向前遍历求得$post\_ans[i]$，

那么有最终答案$ans=\max (ans,post\_ans[i]+dp[i-1])$

以下代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
const int maxn=4e5+50;
const int max_base=31;
int n,a[maxn],pre[maxn],post[maxn];
int ch[31*maxn][2],val[31*maxn],tot;
void init()
{
    tot=1;
    ch[0][0]=ch[0][1]=0;
    val[0]=0;
}
void ins(int x)
{
    int u=0;
    for(int i=max_base;i>=0;i--)
    {
        int c=(x>>i)&1;
        if(!ch[u][c])
        {
            ch[tot][0]=ch[tot][1]=0;
            val[tot]=0;
            ch[u][c]=tot++;
        }
        u=ch[u][c];
    }
    val[u]=x;
}
int query_max(int x)
{
    int u=0;
    for(int i=max_base;i>=0;i--)
    {
        int c=(x>>i)&1;
        if(ch[u][c^1])
            u=ch[u][c^1];
        else
            u=ch[u][c];
    }
    return x^val[u];
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    pre[0]=0;
    for(int i=1;i<=n;i++)
        pre[i]=pre[i-1]^a[i];
    post[n+1]=0;
    for(int i=n;i>=1;i--)
        post[i]=post[i+1]^a[i];
    int dp[maxn],ans;
    init();
    dp[0]=0;
    ins(pre[0]);
    for(int i=1;i<=n;i++)
    {
        dp[i]=max(dp[i-1],query_max(pre[i]));
        ins(pre[i]);
    }
    init();
    ans=0;
    ins(post[n+1]);
    for(int i=n;i>=2;i--)
    {
        ans=max(ans,query_max(post[i])+dp[i-1]);
        ins(post[i]);
    }
    printf("%dn",ans);
    return 0;
}

最后

以上就是风趣大树为你收集整理的HYSBZ - 4260 Codechef REBXOR（前缀和求区间连续异或和，01字典树）的全部内容，希望文章能够帮你解决HYSBZ - 4260 Codechef REBXOR（前缀和求区间连续异或和，01字典树）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。