问题描述
小粽是一个喜欢吃粽子的好孩子。今天她在家里自己做起了粽子。
小粽面前有 (n) 种互不相同的粽子馅儿，小粽将它们摆放为了一排，并从左至右编号为 (1) 到 (n)。第 (i) 种馅儿具有一个非负整数的属性值 (a_i)。每种馅儿的数量都足够多，即小粽不会因为缺少原料而做不出想要的粽子。小粽准备用这些馅儿来做出 (k) 个粽子。
小粽的做法是：选两个整数数 (l,r)，满足 (1le lle rle n)，将编号在 ([l,r]) 范围内的所有馅儿混合做成一个粽子，所得的粽子的美味度为这些粽子的属性值的异或和。（异或就是我们常说的 (mathrm{xor}) 运算，即 C/C++ 中的 ^ 运算符或 Pascal 中的 xor 运算符）
小粽想品尝不同口味的粽子，因此它不希望用同样的馅儿的集合做出一个以上的粽子。
小粽希望她做出的所有粽子的美味度之和最大。请你帮她求出这个值吧！
题解
分类考虑，动态用堆维护前 (k) 大的
显然，题目中涉及到求 (a_l operatorname{xor} a_{l+1} operatorname{xor} cdots operatorname{xor} a_r) 的操作，则一定需要前缀异或
设 (S(i)=a_1 operatorname{xor} a_2 operatorname{xor} cdots operatorname{xor} a_i)，题意则转化为求 (S(i) operatorname{xor} S(j)(i<j)) 的前 (k) 大值的和。
这是一个倒三角求值，可以补为正方形，即 (S(i) operatorname{xor} S(j)) 前 (2k) 大值的和。
建立一个堆，一开始把 (forall i in [1,n],S(i) operatorname{xor} S(j)(i eq j)) 的最大值放到堆里。
每次取堆顶，假设为 (S(i)) 的 (k) 大值，则 pop 之后把 (S(i)) 的第 (k+1) 大值入堆。
以上操作可以通过 ( exttt{0-1 Trie}) 完成。
( exttt{Code})
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 500000 + 7;
int n, k;
int a[maxn], s[maxn];
int ans;
int ch[10000000][2], tot, size[10000000];
//priority_queue <node> q;
struct node {
int val, rk, id;
bool operator < (const node a) const{
return val < a.val;
}
};
priority_queue <node> q;
void Init(void) {
scanf("%lld%lld", &n, &k); k <<= 1;
for(int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
s[i] = s[i - 1] ^ a[i];
}
}
void insert(int x) {
int p = 0;
for(int i = 31; i >= 0; i--) {
int d = (x >> i) & 1;
size[p] ++;
if(!ch[p][d]) ch[p][d] = ++tot;
p = ch[p][d];
}
size[p]++;
}
int query(int x, int t) {
int p = 0, res = 0;
for(int i = 31; i >= 0; i--) {
int d = (x >> i) & 1;
if(ch[p][d ^ 1] == 0) p = ch[p][d];
else if(t <= size[ch[p][d ^ 1]]) p = ch[p][d ^ 1], res += (1ll << i);
else t -= size[ch[p][d ^ 1]], p = ch[p][d];
}
return res;
}
void Work(void) {
for(int i = 0; i <= n; i++) {
insert(s[i]);
}
for(int i = 0; i <= n; i++) {
int rec = query(s[i], 1);
q.push((node){rec, 1, i});
}
while(k--) {
node r = q.top(); q.pop();
ans += r.val;
if(r.rk < n) q.push((node){query(s[r.id], r.rk + 1), r.rk + 1, r.id});
}
ans >>= 1;
printf("%lld
", ans);
}
signed main(void) {
Init();
Work();
return 0;
}