【Trie】Nikitosh 和异或

【参考博客】：

LOJ#10051」「一本通 2.3 例 3」Nikitosh 和异或（Trie

【题目链接】：

https://loj.ac/problem/10051

【题意】：

找出两个不相交区间的异或值相加。

【题解】：

这个题目还是挺有趣的，不是单纯地套模板了。

这个题目类似于最大字段和问题。

首先我们可以预处理出所有的异或前缀和。

区间的异或值，就是两端点异或前缀和的异或值。

还需要处理出

L[t] = max{ Xor[i,j] } 1<= i,j <= t

R[t] = max{ Xor[i,j] } t<= i,j <= n

分别代表两端点的异或最大值，

问题来了，怎么知道上面两个数组的值呢？？？？

其实我们这里需要一点变通，我们其实求区间异或值，其实是两端点的异或前缀和。

如果我们把所有前缀和看成一些数，进行异或值最大化。不就回到最开始01字典树的应用吗？？？

不过我们还需要保留过程中的最大值。

即 L[i] = max{ L[i-1] , Insert_Xor(sum[i]) }

可能插入了当前值，但还是达不到前面一点的最大值。所以需要处理一波。

上面的过程不久像极了最大字段和吗？？？

【代码】：

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N = 4e5+;

const int M = 1e7+3e6;

typedef long long ll;

int Son[M][];

int sum[N],Back[N];

int a[N],n,idx;

ll L[N],R[N];

void Insert(int x){

    int p = ;

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

        int t = x >> i &  ;

        if( !Son[p][t] ) Son[p][t] = ++idx ;

        p = Son[p][t];

    }

}

ll Query(int x){

    int res =  , p =  ;

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

        int t = x >> i &  ;

        if( Son[p][t^] ){

            res += <<i ;

            p = Son[p][t^];

        }else{

            p = Son[p][t];

        }

    }

    return res ;

}

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++)   scanf("%d",&a[i]);

    Insert();

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

        sum[i] = sum[i-] ^ a[i];

        Insert(sum[i]);

        L[i] = max( L[i-] , Query(sum[i]) );

    }

    memset( Son ,  , sizeof Son );

    idx =  ;

    Insert();

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

        sum[i] = sum[i+] ^ a[i];

        Insert(sum[i]);

        R[i] = max( R[i+] , Query(sum[i]) ) ;

    }

    ll ans =  ;

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

        ans = max( ans , L[i]+R[i+] ) ;

    }

    /*

    for(int i=1;i<=n;i++){

        printf("%d , %lld\n",i,L[i]);

    }

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

        printf("%d , %lld\n",i,R[i]);

    }

    */

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

    return ;

}

巴特西

【Trie】Nikitosh 和异或

LOJ#10051」「一本通 2.3 例 3」Nikitosh 和异或（Trie

最新文章

热门文章