设perXor[i]表示1---i的前缀异或值。
那么要得到某一段的异或值，只需要perXor[j] ^ perXor[i - 1]
那么我们把perXor[n]先加入去字典树，然后用perXor[n - 1]去找，找到的就是下标n的贡献。
同理，然后把perXor[n - 1]插进去，用perXor[n - 2]找，就会是下标n - 1的贡献。因为这个时候它可以是
perXor[n - 2] ^ perXor[n - 1]（因为perXor[n - 1]已经在字典树了，）那么这个时候对应的就是a[n - 1] 自己了。
同理它可以是perXor[n - 2] ^ perXor[n]，就是a[n - 1] ^ a[n]了。
当然，它还有个m的限制，这个可以加个删除操作即可。
需要注意的是：
1、unsigned int并不是保留低31位，它是对2^32取模，而2^32有33位。
2、字典树的大小要开好，字典树的struct node *pNext[]只需2个即可。因为状态只有0或1
3、判断第i位是否是1或者0，是((1 << i) & val) >= 1 不要忘记判断，不然re
4、cin、cout请取消同步，卡了我TLE
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string> const int maxn = 5e5 + ;
int a[maxn];
int perXor[maxn];
struct node {
int cnt;
struct node * pNext[];
}tree[maxn * ];
int t;
struct node * create() {
struct node *p = &tree[t++];
// p->cnt = 0;
// for (int i = 0; i <= 9; ++i) {
// p->pNext[i] = NULL;
// }
return p;
}
void toInsert(struct node **T, int val) {
struct node *p = *T;
if (p == NULL) {
p = *T = create();
}
for (int i = ; i >= ; --i) {
int id = (( << i) & val) >= ;
if (p->pNext[id] == NULL) {
p->pNext[id] = create();
}
p = p->pNext[id];
p->cnt++;
}
}
void toDel(struct node **T, int val) {
struct node *p = *T;
if (p == NULL) return;
for (int i = ; i >= ; --i) {
int id = (( << i) & val) >= ;
p = p->pNext[id];
p->cnt--;
}
}
int toFind(struct node *T, int val) {
struct node *p = T;
if (p == NULL) return ;
int ans = ;
// cout << val << endl;
for (int i = ; i >= ; --i) {
int id = (( << i) & val) >= ;
if (p->pNext[!id] && p->pNext[!id]->cnt >= ) {
ans |= ( << i);
p = p->pNext[!id];
} else {
p = p->pNext[id];
}
}
return ans;
}
int listToAdd[maxn];
const LL MOD = (1LL << );
void work() {
int n, m;
cin >> n >> m;
for (int i = ; i <= n; ++i) {
cin >> a[i];
}
for (int i = ; i <= n; ++i) {
perXor[i] = perXor[i - ] ^ a[i];
}
// for (int i = 1; i <= n; ++i) {
// cout << perXor[i] << " " ;
// }
// cout << endl;
// unsigned int t = (1LL << 32);
// cout << t << endl;
long long int ans = ;
struct node *T = NULL;
toInsert(&T, perXor[n]);
int len = ;
listToAdd[++len] = perXor[n];
int cur = ;
// cout << toFind(T, perXor[n]) << endl;
for (int i = n - ; i >= ; --i) {
ans += toFind(T, perXor[i]);
if (ans >= MOD) ans %= MOD;
// cout << toFind(T, perXor[i]) << endl;
toInsert(&T, perXor[i]);
listToAdd[++len] = perXor[i];
if (len - cur + > m) {
toDel(&T, listToAdd[cur++]);
}
}
// cout << endl;
cout << ans << endl;
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
IOS;
work();
return ;
}