算法
(使用字典树) $O(n)$
首先用一个数组 dp[] 来表示 : dp[i] = nums[0] ^ nums[1] ^ .. ^ nums[i-1] , 其中 dp[0] = 0;
则 计算 nums[i : j] 之间的异或和就是 : dp[j] ^ dp[i - 1]
即 每次计入树中加入一个 dp[i] 就要往前找 M 个可以于其异或的 { dp[i`] } 中 查找与dp[i]异或的最大值
所以 每次加入前,若树中的数字个数 == M ,就要在树中删除 dp[i-M-1];
具体看代码实现即可
时间复杂度
- 计算前缀异或是 O(n) 的时间复杂度
- 全部的点都是进入树一次,部分点删除一次 O(n * 31)
综上 总的时间复杂度是 :O(n) 空间复杂度 O(n * 31) = O(n)
C++ 代码
#include <iostream>
#include <bits/stdc++.h>
#include <ctime>
#include <stdlib.h>
using namespace::std;
using LL = long long;
using PII = pair<int,int>;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
int min(int a,int b) {
return a > b ? b : a;
}
int max(int a,int b) {
return a > b ? a : b;
}
class Trie {
private:
Trie* next[2];
int sum;// 该位数字存在的个数
public:
// 定义一个树来存储每一个前缀异或值
Trie() {
for(int i = 0;i < 2;i ++) this->next[i] = nullptr;
sum = 0;
return ;
}
int query(int x) {
int r = 1 << 30;
// x 的第 i 位 的数字 x & (r) > 0
Trie* root = this;
int res = 0;
while(r) {
int t = (x & r) > 0 ? 0 : 1;
// 获得较大值 t 应该存在的值
if(root->next[t]) {
res = res * 2 + 1;
root = root->next[t];
} else {
res <<= 1;
root = root->next[t ^ 1];
}
r >>= 1;
}
return res;
}
void insert(int x) {
Trie* root = this;
int r = 1 << 30;
while(r) {
int t = (x & r) > 0 ? 1 : 0;
if(root->next[t]) {
root = root->next[t];
} else {
Trie* new_r = new Trie();
root->next[t] = new_r;
root = root->next[t];
}
root->sum ++;
r >>= 1;
}
return ;
}
void erase(int x) {
// 在树中删除 x
Trie* root = this;
int r = 1 << 30;
while(r) {
int t = (x & r) > 0 ? 1 : 0;
if(root->next[t]->sum == 1) {
root->next[t] = nullptr;
return ;
} else {
root->next[t]->sum --;
root = root->next[t];
}
r >>= 1;
}
return ;
}
};
const int len = 1e5 + 5;
int dp[len];
int main() {
int N,M;
scanf("%d %d",&N,&M);
Trie* root = new Trie();
int res = 0;
dp[0] = 0;
scanf("%d",&dp[1]);
// dp[i] = nums[0] ^ nums[1] ^ .. ^ nums[i-1]
for(int i = 1;i < N;i ++) {
scanf("%d",&dp[i + 1]);
dp[i + 1] ^= dp[i];
}
root->insert(dp[0]);
for(int i = 1;i <= M;i ++) {
root->insert(dp[i]);// 加入
// cout<<root->query(dp[i])<<endl;
res = max(root->query(dp[i]),res);// 更新
}
for(int i = M + 1;i <= N;i ++) {
root->insert(dp[i]);// 加入
root->erase(dp[i-M - 1]);// 删除
// cout<<root->query(dp[i])<<endl;
res = max(root->query(dp[i]),res);// 更新
}
cout<<res<<endl;
return 0;
}