给定一个非负整数数列 a,初始长度为 N。
请在所有长度不超过 M 的连续子数组中,找出子数组异或和的最大值。
子数组的异或和即为子数组中所有元素按位异或得到的结果。
注意:子数组可以为空。
输入格式
第一行包含两个整数 N,M。
第二行包含 N 个整数,其中第 i 个为 ai。
输出格式
输出可以得到的子数组异或和的最大值。
数据范围
对于 20% 的数据,1≤M≤N≤100
对于 50% 的数据,1≤M≤N≤1000
对于 100% 的数据,1≤M≤N≤105,0≤ai≤231−1
输入样例:
3 2
1 2 4
输出样例:
6
```
//储备知识:树,前缀和的思想(异或和)
//看到区间,就应该想到前缀和,不妨设数组a前k项的异或和(s[k]),k+n项的异或和为s[k+n],因为异或运算具有结合性,自身异或自身==0,任何数与0异或等于它本身,所以s[k]^s[k+n]就是第k+1个数字到第k+n个数字的异或
// 直接把y总的标准代码拿来了。。。。o(n)=nlogn
//这个题因为有子区间限制长度,所以我们需要用滑动窗口实现删除一棵树并且加上下一棵新的树范围就是s[max(i-m,0)]~s[i]
include [HTML_REMOVED]
include [HTML_REMOVED]
include [HTML_REMOVED]
using namespace std;
const int N=100010*31;//有100000棵树,每棵树31个节点!
int son[N][2],a[100010],s[100010],n,idx=0,cnt[N];
//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]//除了最后一位&的是1,其他都是0,所以就是查询最后一位。
if (!son[p][u]) son[p][u]=idx; //如果p的子节点没有u,那就新建立一个节点
p=son[p][u];//这个节点就是上一个节点的子节点,这里写的很明白,
cnt[p]+=v;//这个地方的处理有点像并查集,都是子承父的过程。 (学习的本质!),删除的话就是-1操作
//cnt数组存当前编号为p的节点出现的次数
}
}int query (int x){
//s[i]的“势力范围”(就是s[i]前边的) 是s[max(i-m,0)]~s[i] 的逐个异或看看最大值。
int p=0,res=0;
for (int i=30;i>=0;i–){
int u=x>>i[HTML_REMOVED]
if (cnt[son[p][!u]])//即p的儿子有与u的当前位相反的,那就顺着这条路走。(因为位数越靠前的权重越大)
{
res=res2+1;//上一层2+上异或的这一个
p=son[p][!u];//当前节点就走向与之相反的子节点的分枝里去了,分枝里边还能再分
}
else {
res=2;//因为儿子没有与当前位置相反的数字,没法异或出来1,那就在原来的基础上2呗。
p=son[p][u];//节点往下沉,就只能到son[p][n]了
}
}
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);
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);
}//本质上就是一个栽树挪树的过程
}
初学markdown可以用
\``` 三个点把代码框起来, 避免和html语法冲突