望指正,谢谢
//仅限于对y总代码的解答,可能有错望指正
#include <iostream>
#include <cstring>
#include <algorithm>
//注:全局变量初始值为0(我一开始以为是随机值,麻了)
using namespace std;
const int N=100010*31,M=100010;
int n,m;
int s[M];
int son[N][2],cnt[N],idx;//idx就是用来申请节点的,必须用全局变量(y总的思路是树,但是s[i]的节点都不是连续的)
void insert(int x,int v){//insert,将数据x变成树的一个分支,v=1,树对应的相关节点可用,v=-1,树的相关节点不可用
int p=0;
for(int i=30;i>=0;i--){
int u=x>>i&1;//思想:将x变成二进制数组提取出第i位的数字
if(!son[p][u]) son[p][u]=++idx;//节点不存在,将节点赋值,表示节点存在
p=son[p][u];//跳到下一个节点所在的位置
cnt[p]+=v;//节点是否可用
}
}
int query(int x){//异或算法
int p=0,res=0;
for(int i=30;i>=0;i--){
int u=x>>i&1;
if(cnt[son[p][!u]]) p=son[p][!u],res=res*2+1;//优先走该节点相异的节点(cnt[0]一直为零,所以可以同时判断相异节点是否存在)
else p=son[p][u],res*=2;//相异节点不存在,走相同节点,res*=2是因为一个点是一个二进制
}
return res;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
int x;
cin>>x;
s[i]=s[i-1]^x;//前缀异或和(大家都听了课吧。。。没听的去听一下,解释起来要好多,不想打字)
}
int res=0;
insert(s[0],1);//先申请出一个树的分支,不然第一个query不好异或(是s[0]=0,所以不管是谁和他异或都是他自己)
for(int i=1;i<=n;i++){
if(i>m) insert(s[i-m-1],-1);//滑动窗口,使得超出m范围分支不可用,一次踢走一个
res=max(res,query(s[i]));//更新结果,保留最大值
insert(s[i],1);//每次插入一个树的分支
}
cout<<res;
return 0;
}
我不晓得对不对,望指正