首页 > 代码库 > bzoj4260 Codechef REBXOR

bzoj4260 Codechef REBXOR

2024-10-15 08:43:40   219人阅读

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。

 

正解：可持久化$trie$树。

这是一道板子题，然而因为常数调了一晚上。。

直接用可持久化$trie$树来维护区间异或最大和就行了。不多说了。。

 

 1 //It is made by wfj_2048~ 2 #include <algorithm> 3 #include <iostream> 4 #include <complex> 5 #include <cstring> 6 #include <cstdlib> 7 #include <cstdio> 8 #include <vector> 9 #include <queue>10 #include <stack>11 #include <map>12 #include <set>13 #define M (15000010)14 #define N (500010)15 #define il inline16 #define RG register17 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)18 19 using namespace std;20 21 int ch[M][2],sum[M],rt[N],a[N],b[N],n,sz,res,ans;22 23 const int STRSIZE=int(4e7);24 char in1[STRSIZE], *in=in1, *tempend;25 26 il int gi(){27     char c=*(in++); while(c<‘0‘ || c>‘9‘) c=*(in++); RG int x=c-‘0‘;28     c=*(in++); while (c>=‘0‘ && c<=‘9‘) x=x*10+c-‘0‘,c=*(in++); return x;29 }30 31 il int max(RG int &a,RG int &b){ return a>b ? a : b; }32 33 il void insert(RG int x,RG int &now,RG int &v){34     now=++sz; RG int y=now;35     for (RG int i=29,tmp;i>=0;--i){36     tmp=v>>i&1,ch[y][0]=ch[x][0],ch[y][1]=ch[x][1];37     ch[y][tmp]=++sz,x=ch[x][tmp],y=ch[y][tmp],sum[y]=sum[x]+1;38     }39     ch[y][0]=ch[x][0],ch[y][1]=ch[x][1]; return;40 }41 42 il int query(RG int x,RG int y,RG int &v){43     RG int ans=0;44     for (RG int i=29,tmp;i>=0;--i){45     tmp=(v>>i&1)^1;46     if (sum[ch[y][tmp]]-sum[ch[x][tmp]]) ans|=1<<i,x=ch[x][tmp],y=ch[y][tmp];47     else x=ch[x][tmp^1],y=ch[y][tmp^1];48     }49     return ans;50 }51 52 il void work(){53     n=gi(); for (RG int i=1;i<=n;++i) a[i]=gi(),b[i]=b[i-1]^a[i],insert(rt[i-1],rt[i],b[i]);54     for (RG int i=n-1;i;--i){55     res=max(res,query(rt[i],rt[n],b[i]));56     ans=max(ans,res+max(b[i],query(rt[0],rt[i],b[i])));57     }58     printf("%d\n",ans); return;59 }60 61 int main(){62     File("xor");63     tempend=in+STRSIZE;64     fread(in,1,STRSIZE,stdin);65     work();66     return 0;67 }

 

bzoj4260 Codechef REBXOR


联系
我们