BZOJ 4260 Codechef REBXOR (区间异或和最值) (01字典树+DP)

时间：2021-09-23 05:41:37

<题目链接>

题目大意：
给定一个序列，现在求出两段不相交的区间异或和的最大值。

解题分析：

区间异或问题首先想到01字典树。利用前缀、后缀建树，并且利用异或的性质，相同的两个数异或变成0，从而将前缀操作转化为区间操作，比如：$(a_1 \oplus a_2)\oplus(a_1 \oplus a_2 \oplus a_3 \oplus a_4) = a_3 \oplus a_4$。然后利用简单的$dp$，$predp[i]$记录前$[1~i]$ 任意区间的区间异或最大值(注意不是前缀)，$nxtdp$同理记录后缀区间的最大值。

本题空间卡得比较紧，所以没有另外用一个$val[now]$数组记录Trie树前缀节点所表示的值，而是在$query$中用$ans$代替。

#include <bits/stdc++.h>

using namespace std;

const int N = 4e5+;

typedef long long ll;

ll n,pos=,arr[N],nxt[N*][],predp[N],nxtdp[N];

template<typename T>

inline T read(T&x) {

    x = ;int f = ; char ch = getchar();

    while(ch<'' || ch>'') { if(ch == '-') f=-; ch=getchar(); }

    while(ch>='' && ch<='') { x=x*+ch-''; ch=getchar(); }

    return x*f;

}

void Insert(ll x){

    int now=;

    for(int i=;i>=;i--){

        int to=(x>>i)&;

        if(!nxt[now][to])nxt[now][to]=++pos;

        now=nxt[now][to];

    }

}

ll query(ll x){

    int now=;ll ans=;

    for(int i=;i>=;i--){

        int to=(x>>i)&;

        if(nxt[now][to^])now=nxt[now][to^],ans+=(<<i);   //因为最终异或得到的答案就是x中所不包含的数位

        else now=nxt[now][to];

    }

    return ans;

    //return x^val[now];      因为本题空间卡得紧，所以就不能写成这种形式

}

int main(){

    read(n);

    for(int i=;i<=n;i++)read(arr[i]);

    for(int cur=,i=;i<=n;i++){

        Insert(cur^=arr[i]);

        predp[i]=max(query(cur),predp[i-]);  //因为一个数被异或两次等于0，所以这里利用Trie树的前缀操作来实现区间操作

    }//得到 i 的前缀区间异或和的最大值

    memset(nxt,,sizeof(nxt));

    for(int cur=,i=n;i>=;i--){

        Insert(cur^=arr[i]);

        nxtdp[i]=max(query(cur),nxtdp[i+]);

    }//得到 i 的后缀异或区间和的最大值

    ll ans=-;

    for(int i=;i<=n;i++)ans=max(ans,predp[i]+nxtdp[i]);

    printf("%lld\n",ans);

}

2019-03-02

相关文章