【bzoj4260】REBXOR

  • 本文为博主原创,未经许可不得转载

从右往左枚举r1,在左边找最优的l1(可持久化字典树实现)

同时维护右边l2和r2的最优值,这样就能包含所有情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 400100
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
using namespace std;
int n,Rmax,ans,cnt,a[MAXN],root[MAXN],sum[MAXN*35],son[MAXN*35][2];
inline int read(){
int x=0,f=1; char ch=getchar();
while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch=getchar();}
while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
void insert(int &root,int last,int v){
root=++cnt; int now=root;
for(int i=30;i>=0;--i){
son[now][0]=son[last][0];
son[now][1]=son[last][1];
int x=(v&(1<<i))>>i;
son[now][x]=++cnt;
now=son[now][x];
last=son[last][x];
sum[now]=sum[last]+1;
}
}
int query(int l,int r,int v){
int ret=0;
for(int i=30;i>=0;--i){
int x=(v&(1<<i))>>i;
if(sum[son[r][x^1]]-sum[son[l][x^1]]){
ret+=(1<<i);
l=son[l][x^1],r=son[r][x^1];
}
else l=son[l][x],r=son[r][x];
}
return ret;
}
int main(){
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
n=read()+1;
for(int i=2;i<=n;++i) a[i]=a[i-1]^read();
for(int i=1;i<=n;++i) insert(root[i],root[i-1],a[i]);
for(int i=n-1;i;--i){
cmax(Rmax,query(root[i],root[n],a[i]));
cmax(ans,Rmax+query(root[0],root[i],a[i]));
}
printf("%d\n",ans);
return 0;
}
文章目录
,