Nikitosh 和异或 LibreOJ - 10051
题解：
本题题意是找到两个不相交区间，使得他们的异或和最大。
思路：
本题就是强硬套 01Trie 树即可。
先把区间预处理一下，处理一个异或前缀和一个异或后缀。之后dp【i】。表示
i
i
i 以前的最大异或和。（这里因为每次查看时，都是把一个前缀加入）
所以可以利用trie，查找一个区间的最大异或值。转换为了求两个数的异或值，就是常规操作了。两个数的最大异或和，传送门
最后再，反着来一遍即可。
反思：
本题要求你求两个区间的异或和。可以先想怎么求一个区间的异或和。之后在想怎么合并。
AC
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#define For(i,x,y) for(int i=(x); i<=(y); i++)
#define mst(x,a) memset(x,a,sizeof(x))
using namespace std
;
const int maxnode
=2e7+10;
const int sigma_size
=2;
int sz
=2;
int ch
[maxnode
][sigma_size
];
void clear(){sz
=2;mst(ch
[1],0);}
void insert(int str
){
int u
=1;
for(int i
=31; i
>=0; i
--){
int k
=(str
>>i
)&1;
if(!ch
[u
][k
]){
mst(ch
[sz
],0);
ch
[u
][k
]=sz
++;
}
u
=ch
[u
][k
];
}
}
int find(int str
){
int u
=1,res
=0;
for(int i
=31; i
>=0; i
--){
int k
=(str
>>i
)&1;
if(ch
[u
][k
^1]){
res
+=(1<<i
);
u
=ch
[u
][k
^1];
}
else u
=ch
[u
][k
];
}
return res
;
}
const int maxn
=4e5+10;
int dp
[maxn
];
int pre
[maxn
],suf
[maxn
],a
[maxn
];
int main()
{
ios
::sync_with_stdio(0);cin
.tie(0);cout
.tie(0);
clear();
int n
;cin
>>n
;
For(i
,1,n
){
cin
>>a
[i
];
pre
[i
]=pre
[i
-1]^a
[i
];
}
for(int i
=n
; i
>=1; i
--)suf
[i
]=suf
[i
+1]^a
[i
];
For(i
,1,n
){
insert(pre
[i
]);
dp
[i
]=max(dp
[i
-1],find(pre
[i
]));
}
clear();
int ans
=0;
for(int i
=n
; i
>=1; i
--){
insert(suf
[i
]);
ans
=max(ans
,dp
[i
-1]+find(suf
[i
]));
}
cout
<<ans
<<endl
;
return 0;
}
