include [HTML_REMOVED]
include [HTML_REMOVED]
include [HTML_REMOVED]
using namespace std;
const int N=100010*31;
//int son[N][2],cnt[N],a[100010],n,idx,s[100010];
// 整体思路 字典树求最大异或对的做法
// 将子数组l~r的异或和a[l]^…^a[r] 转化为前缀异或和数组(s[r]^s[l-1])
// 遍历s数组每轮内查询s[i]在合法范围的最大异或和 最后得到结果
// ps:合法范围就是s[max(i-m,0)]~s[i]
int son[N][2],a[100010],s[100010],n,idx,cnt[N];
//son数组 第一维是节点编号第二维是0或1儿子
//存的是p节点的0或1儿子的节点编号
//cnt数组当前存编号为p的节点出现的次数
void insert (int x,int v){
//插入兼删除函数 通过v的正反实现插入与删除
int p=0;
for (int i=30;i>=0;i–){
int u=x>>i[HTML_REMOVED]
if (!son[p][u]) son[p][u]=idx;
p=son[p][u];
cnt[p]+=v;
//cnt数组存当前编号为p的节点出现的次数
}
}
int query (int x){
//查询x最大异或和
int p=0,res=0;
for (int i=30;i>=0;i–){
int u=x>>i[HTML_REMOVED]
if (cnt[son[p][!u]]) {
//由于我们的x可求异或和的范围不是所有s
//所以不是if (son[p][!u])
//而是cnt[son[p][!u]]当前可异或节点的出现次数
res=res2+1;
p=son[p][!u];
}
else {
res=2;
p=son[p][u];
}
}
return res;
}
int main()
{
int m;
cin>>n>>m;
for (int i=1;i<=n;i){
cin>>a[i];
s[i]=s[i-1]^a[i];
}
insert(s[0],1);
//子数组可以为空 插入0
int res=0;
for (int i=1;i<=n;i++){
if (i>m) insert(s[i-m-1],-1);
//s[i]可求异或合法范围是s[max(i-m,0)]~s[i]
//要及时把超出范围的数去掉
res=max(res,query(s[i]));
insert(s[i],1);
}
cout <<res;
}
作者:蓬蒿人
链接:https://www.acwing.com/solution/content/48678/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。