Codechef REBXOR(异或前缀tire

65 阅读 0 评论 43 点赞

我是靠谱客的博主雪白外套，最近开发中收集的这篇文章主要介绍Codechef REBXOR(异或前缀tire，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

#include<bits/stdc++.h>
using namespace std;
// #define int long long
const int N=4e5+10;
int n,a[N],t[N*20][2],cnt=0;
int pre[N],max1[N],max2[N];
void insert(int x){
    int p=0;
    for(int i=31;i>=0;i--){
        int now=(x&(1<<i))==0?0:1;
        if(t[p][now]==0) t[p][now]=++cnt;
        p=t[p][now];
    }
}
int find(int x){
    int p=0,tp=0;
    for(int i=31;i>=0;i--){
        int now=(x&(1<<i))==0?0:1;
        now^=1;
       if(t[p][now]==0) p=t[p][now^1];
       else p=t[p][now],tp+=(1<<i);
    }
    return tp;
}
int32_t main(){
    scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    pre[0]=0;insert(0);
    for(int i=1;i<=n;i++){
        pre[i]=pre[i-1]^a[i];
        insert(pre[i]);
        max1[i]=max(max1[i-1],find(pre[i]));
    }
    memset(t,0,sizeof t);cnt=0;
    pre[n+1]=0;insert(0);
    for(int i=n;i>=1;i--){
        pre[i]=pre[i+1]^a[i];
        insert(pre[i]);
        max2[i]=max(max2[i+1],find(pre[i]));
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        ans=max(ans,max1[i]+max2[i+1]);
    }
    cout<<ans<<endl;


}