题目描述

给定一个非负整数数列 $a=(a_1,a_2,...,a_n)$，初始长度为 $N$。

请在所有长度不超过 $M$ 的连续子数组中，找出子数组异或和的最大值。 子数组的异或和即为子数组中所有元素按位异或得到的结果。

注意：子数组可以为空。

输入格式

第一行包含两个正整数 $N$,$M$。

第二行包含 $N$ 个整数 $a_1,a_2,...,a_n$。

输出格式

输出可以得到的子数组异或和的最大值。

输入输出样例

输入

3 2
1 2 4

输出

6

数据范围

对于 $20\%$ 的数据，$1\le M\le N\le100

对于 $50\%$ 的数据，$1\le M\le N\le1000$

对于 100% 的数据，$1\le M\le N\le10^5$，$0\le a_i\le2^{31}-1$

只有 $75pts$，救救孩子吧：

#include<bits/stdc++.h>
using namespace std;
int n,m,tot,ans,a[100005],pre[100005],cnt[1000005],trie[3100035][2];
void insert(int x){
	int cur = 0;
	for (int i = 30; i >= 0; i--){
		int u = x >> i & 1;
		cnt[cur]++;
		if (!trie[cur][u]) trie[cur][u] = ++tot;
		cur = trie[cur][u];
	}
	cnt[cur]++;
}
void erase(int x){
	int cur = 0;
	for (int i = 30; i >= 0; i--){
		int u = x >> i & 1;
		cnt[cur]--;
		cur = trie[cur][u];
	}
	cnt[cur]--;
}
int query(int x){
	int cur = 0,ans = 0;
	for (int i = 30; i >= 0; i--){
		int u = x >> i & 1;
		if (trie[cur][u ^ 1] && cnt[trie[cur][u ^ 1]]){
			ans += 1 << i;
			cur = trie[cur][u ^ 1];
		} 
		else cur = trie[cur][u];
	}
	return ans;
}
int main(){
	cin >> n >> m;
	for (int i = 1; i <= n; i++){
		cin >> a[i];
		pre[i] = pre[i - 1] ^ a[i];
	}
	insert(0);
	for (int i = 1; i <= n; i++){
		ans = max(ans,query(pre[i]));
		if (i >= m) erase(pre[i - m]);
		insert(pre[i]);
	}
	cout << ans;
	return 0;
}