常州市城投建设工程招标有限公司网站北京市住房建设投资中心网站

给定一个非负整数数列 a，初始长度为 N。

请在所有长度不超过 M 的连续子数组中，找出子数组异或和的最大值。

子数组的异或和即为子数组中所有元素按位异或得到的结果。

注意：子数组可以为空。

输入格式

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

第二行包含 N 个整数，其中第 i 个为 ai。

输出格式

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

数据范围

对于 20% 的数据，1≤M≤N≤100
对于 50% 的数据，1≤M≤N≤1000
对于 100% 的数据，1≤M≤N≤10^5,0≤ai≤2^31−1

输入样例：

3 2
1 2 4

输出样例：

6

 这里用到trie树存储数据，具体可参考最大异或对的解法

http://t.csdn.cn/DD8lX

和trie树的模板参考http://t.csdn.cn/wyvow

也是声明son数组，从第31位开始存。这里用到了前缀异或和，当超出m的限制时需要将区间往后移，所以额外声明cnt数组来判断该点是否存在所求的区间里，于是在插入操作时额外定义一个参数v表示插入或者删去。

 以下是代码详解