淘宝软件营销网站建设友情链接源码

给定一个非负整数数列 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表示插入或者删去。

 以下是代码详解