#2356. 异或粽子

    ID: 2356 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>PROV赛事:contest401来源:qoj.ac数据:公开样例前缀和二分

异或粽子

异或粽子

题目描述

2019 全国青少年信息学奥林匹克竞赛联合省代表队选拔 第一试异或粽子(xor) 异或粽子(xor) 【题目描述】 小粽是一个喜欢吃粽子的好孩子。今天她在家里自己做起了粽子。 小粽面前有n 种互不相同的粽子馅儿,小粽将它们摆放为了一排,并从左至右编 号为1 到n。第i 种馅儿具有一个非负整数的属性值ai。每种馅儿的数量都足够多,即 小粽不会因为缺少原料而做不出想要的粽子。小粽准备用这些馅儿来做出k 个粽子。 小粽的做法是:选两个整数数l, r,满足1 ≤l ≤r ≤n,将编号在[l, r] 范围内的所 有馅儿混合做成一个粽子,所得的粽子的美味度为这些粽子的属性值的.异.或和。(异或 就是我们常说的xor 运算,即C/C++ 中的ˆ 运算符或Pascal 中的xor 运算符) 小粽想品尝不同口味的粽子,因此它不希望用同样的馅儿的集合做出一个以上的 粽子。 小粽希望她做出的所有粽子的美味度之和最大。请你帮她求出这个值吧! 【输入格式】 从文件xor.in 中读入数据。 第一行两个正整数n, k,表示馅儿的数量,以及小粽打算做出的粽子的数量。 接下来一行为n 个非负整数,第i 个数为ai,表示第i 个粽子的属性值。 对于所有的输入数据都满足:1 ≤n ≤5 × 105, 1 ≤k ≤min {n(n−1) 2 , 2 × 105} , 0 ≤ai ≤ 4, 294, 967, 295。 【输出格式】 输出到文件xor.out 中。 输出一行一个整数,表示小粽可以做出的粽子的美味度之和的最大值。 【样例1 输入】 3 2 1 2 3 【样例1 输出】 6 【样例1 解释】 小粽可以选取[3, 3], [1, 2] 两个区间的馅儿做成粽子,两个粽子的美味度都为3,和 为6。可以证明不存在比这更优的方案。 第2 页 共9 页

2019 全国青少年信息学奥林匹克竞赛联合省代表队选拔 第一试异或粽子(xor) 【样例2】 见选手目录下的xor/xor2.in 与xor/xor2.ans。 【子任务】 测试点 n k 1,2,3,4,5,6,7,8 ≤103 ≤103 9,10,11,12 ≤5 × 105 13,14,15,16 ≤103 ≤2 × 105 17,18,19,20 ≤5 × 105 第3 页 共9 页

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3 2
1 2 3
6