题目描述
给定一个非负整数数列 a,初始长度为 N。
请在所有长度不超过 M 的连续子数组中,找出子数组异或和的最大值。
子数组的异或和即为子数组中所有元素按位异或得到的结果。
注意:子数组可以为空。
样例
3 2
1 2 4
6
算法
Trie树 $O(n)$
前置知识:Trie树,异或性质(前缀和)。
对于一个连续区间每个数可以从高到低位,建Trie树。把连续的一些数扔进Trie树,这些数中的任一个与x异或,会得到一个值,求最大的这个值:二进制位从高到低查找Trie树,如果x当前位为0,就找1的,否则找0的,这样贪心最大,当然如果找不到就只能找一样的了。
此时对数组a求得异或前缀和,从后向前遍历,每次把当前数扔进Trie树(注意维护长度为M),只要求出树上这些数与i-1位置上的数异或最大值即可。
时间复杂度
添加删除修改都是31次,所以是$O(1)$,每个i最多运行添加修改删除各一次,是$O(n)$。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
struct E{
int l,r,c,num;
}e[3000020];
int n,m,a[100020],b[100020],cnt;
void add(int x){
int cur=0;
for(int i=(1<<30);i!=0;i>>=1){
e[cur].c++;
if(i&x){
if(e[cur].r==0){
e[++cnt]=(E){0,0,0};
e[cur].r=cnt;
}
cur=e[cur].r;
}
else{
if(e[cur].l==0){
e[++cnt]=(E){0,0,0};
e[cur].l=cnt;
}
cur=e[cur].l;
}
}
e[cur].c++;
e[cur].num=x;
}
int find(int x){
int cur=0;
for(int i=(1<<30);i!=0;i>>=1){
if(i&x){
if(e[cur].l&&e[e[cur].l].c){
cur=e[cur].l;
}
else{
cur=e[cur].r;
}
}
else{
if(e[cur].r&&e[e[cur].r].c){
cur=e[cur].r;
}
else{
cur=e[cur].l;
}
}
}
return e[cur].num;
}
void del(int x){
int cur=0;
for(int i=(1<<30);i!=0;i>>=1){
e[cur].c--;
if(i&x){
cur=e[cur].r;
}
else{
cur=e[cur].l;
}
}
e[cur].c--;
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
a[i]^=a[i-1];
}
int ans=0;
for(int i=n;i>=1;i--){
add(a[i]);
if(n-i+1>m){
del(a[i+m]);
}
//cout<<find(a[i-1])<<endl;
ans=max(ans,find(a[i-1])^a[i-1]);
}
printf("%d\n",ans);
return 0;
}
dalao,问一下ans=max(ans,find(a[i-1])^a[i-1]);这里是为什么是i-1,那i=1的时候不是会找a[0]=0的答案
我明白了,前缀和里你还对a[0]操作了
tql