首页 > 代码库 > bzoj4260 Codechef REBXOR
bzoj4260 Codechef REBXOR
Description
Input
输入数据的第一行包含一个整数N,表示数组中的元素个数。
第二行包含N个整数A1,A2,…,AN。
Output
输出一行包含给定表达式可能的最大值。
Sample Input
5
1 2 3 1 2
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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。