代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010 * 31, M = 100010;
int n, m;
int s[M];
int son[N][2], cnt[N], idx;
void insert(int x, int v)//v取正1表示添加x,取-1表示删除x
{
int p = 0;
for (int i = 30; i >= 0; i -- )
{
int u = x >> i & 1;
if (!son[p][u]) son[p][u] = ++ idx;
p = son[p][u];
cnt[p] += v;
}
}
int query(int x)//query(s[i])找出s[i]^s[i-1],s[i]^s[i-2]...s[i]^s[0]中的最大值
{
int res = 0, p = 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;
else p = son[p][u], res = res * 2;
}
return res;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ )
{
int x;
scanf("%d", &x);
s[i] = s[i - 1] ^ x;
}
int res = 0;
insert(s[0], 1);
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);
}
printf("%d\n", res);
return 0;
}
一开始遇到的问题:
1.为什么遍历所有的变长前缀异或和只用$O_{(N)}$,而不是像正常的前缀和需要$O_{(N^2)}$?
like:
for(int i=n;i>=1;i--){
for(int j=i-1;j>=0;j--){
int SecSum=pre[i]-pre[j];
}
}
因为当query(s[i], 1)
时,trie树中已经存储的有s[i-1],s[i-2]...s[0]
,与最大异或对相同,query
会返回s[i]
与trie树中已有的所有异或的最大值,而s[i]^s[i-1]
,因为s[i-1]
的部分都是相同的,所以就相当于前缀和的s[i]-s[i-1]
,至此,所有的区间异或和都会被计算。
2.关于限定长度M的处理
可以将其理解为一个滑动窗口。
假设当$i=m+1$时:根据if (i > m) insert(s[i - m - 1], -1)
会删除掉trie树中s[0]
,含义就是s[m+1]
这个区间插入trie树后不能再和s[0]
异或后计算最大值。根据前面的理解,s[i]^s[j]
是从a[j+1]~a[i]
的前缀异或和,长度为$i-(j+1)+1$,s[m+1]
表示的是a[1]~a[m+1]
的异或和,长度大于m,不符合条件,所以让s[m+1]
最小只能异或下标大于等于1的,也就限制了只在长度小于等于M的区间中找最大值。