#2030. 「十二省联考2019」异或粽子

内存限制:1024 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: StudyingFather

题目描述

小粽是一个喜欢吃粽子的好孩子。今天她在家里自己做起了粽子。

小粽面前有 n 种互不相同的粽子馅儿,小粽将它们摆放为了一排,并从左至右编号为 1 n 。第 i 种馅儿具有一个非负整数的属性值 a_i 。每种馅儿的数量都足够多,即小粽不会因为缺少原料而做不出想要的粽子。小粽准备用这些馅儿来做出 k 个粽子。

小粽的做法是:选两个整数数 l,r ,满足 1\le l\le r\le n ,将编号在 [l,r] 范围内的所有馅儿混合做成一个粽子,所得的粽子的美味度为这些粽子的属性值的异或和。(异或就是我们常说的 \mathrm{xor} 运算,即 C/C++ 中的 ^ 运算符或 Pascal 中的 xor 运算符)

小粽想品尝不同口味的粽子,因此它不希望用同样的馅儿的集合做出一个以上的粽子。

小粽希望她做出的所有粽子的美味度之和最大。请你帮她求出这个值吧!

输入格式

从标准输入读入数据。

第一行两个正整数 n,k ,表示馅儿的数量,以及小粽打算做出的粽子的数量。

接下来一行为 n 个非负整数,第 i 个数为 a_i ,表示第 i 个粽子的属性值。

输出格式

输出到标准输出。

输出一行一个整数,表示小粽可以做出的粽子的美味度之和的最大值。

样例

样例输入 1

3 2
1 2 3

样例输出 1

6

样例说明

小粽可以选取 [3,3],[1,2] 两个区间的馅儿做成粽子,两个粽子的美味度都为 3 ,和为 6 。可以证明不存在比这更优的方案。

样例 2

见附加文件 2.in/ans

数据范围与提示

测试点 n k
1\sim 8 \le 10^{3} \le 10^{3}
9\sim 12 \le 5 \times 10^{5}
13\sim 16 \le 10^{3} \le 2 \times 10^{5}
17\sim 20 \le 5 \times 10^{5}

对于所有的输入数据都满足: 1\le n \le 5 \times 10^{5},1\le k\le \min\left\{\frac{n(n-1)}{2},2 \times 10^{5}\right\},0\le a_i \le 4,294,967,295