$ color{#0066ff}{ 题目描述 }$
小粽是一个喜欢吃粽子的好孩子。今天她在家里自己做起了粽子。
小粽面前有 (n) 种互不相同的粽子馅儿，小粽将它们摆放为了一排，并从左至右编号为 (1) 到 (n)。第 (i) 种馅儿具有一个非负整数的属性值 (a_i)。每种馅儿的数量都足够多，即小粽不会因为缺少原料而做不出想要的粽子。小粽准备用这些馅儿来做出 (k) 个粽子。
小粽的做法是：选两个整数数 (l), (r)，满足 (1 leqslant l leqslant r leqslant n)，将编号在 ([l, r] 范围)内的所有馅儿混合做成一个粽子，所得的粽子的美味度为这些粽子的属性值的异或和。（异或就是我们常说的 xor 运算，即 C/C++ 中的 ˆ 运算符或 Pascal 中的 xor 运算符）
小粽想品尝不同口味的粽子，因此它不希望用同样的馅儿的集合做出一个以上的 粽子。
小粽希望她做出的所有粽子的美味度之和最大。请你帮她求出这个值吧！
(color{#0066ff}{输入格式})
第一行两个正整数 (n),(k)，表示馅儿的数量，以及小粽打算做出的粽子的数量。
接下来一行为 (n) 个非负整数，第 (i) 个数为 (a_i)，表示第 (i) 个粽子的属性值。 对于所有的输入数据都满足：(1 leqslant n leqslant 5 imes 10^5), (1 leqslant k leqslant minleft{frac{n(n-1)}{2},2 imes 10^{5} ight})(0 leqslant a_i leqslant 4 294 967 295)
(color{#0066ff}{输出格式})
输出一行一个整数，表示小粽可以做出的粽子的美味度之和的最大值。
(color{#0066ff}{输入样例})
3 2
1 2 3
(color{#0066ff}{输出样例})
6
(color{#0066ff}{数据范围与提示})
| 测试点 | (n) | (k) |
|---|---|---|
| (1), (2), (3), (4), (5), (6), (7), (8) | (leqslant 10^3) | (leqslant 10^3) |
| (9), (10), (11), (12) | (leqslant 5 imes 10^5) | (leqslant 10^3) |
| (13), (14), (15), (16) | (leqslant 10^3) | (leqslant 2 imes 10^5) |
| (17), (18), (19),(20) | (leqslant 5 imes 10^5) | (leqslant 2 imes 10^5) |
(color{#0066ff}{题解})
显然可以转换一下，求一下前缀和，问题就变成了前k大两两异或和
建立一个可持久化01Trie，发现可以类似权值线段树求第k大，然后就水了。。。
用线段树维护每一个(s_i)的最优的(s_j(j<i))使得(s_i xor s_j)最大
每次加上线段树最大值，然后找到最大值取到的位置，在01Trie上找次大的在线段树上更新就行了
蒟蒻考场上只写了60的暴力。。。。
然而本题貌似卡指针，反正数组过了23333
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define LL long long
LL in() {
char ch; LL x = 0, f = 1;
while(!isdigit(ch = getchar()))(ch == '-') && (f = -f);
for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 1) + (x << 3) + (ch ^ 48));
return x * f;
}
template<class T> bool chkmax(T &a, const T &b) { return a < b? a = b, 1 : 0; }
template<class T> bool chkmin(T &a, const T &b) { return b < a? a = b, 1 : 0; }
const int maxn = 5e5 + 100;
struct SGT {
protected:
struct node {
node *ch[2];
int l, r, id;
LL val;
node(int l = 0, int r = 0, LL val = 0): l(l), r(r), val(val) { ch[0] = ch[1] = NULL; }
void upd() { val = std::max(ch[0]->val, ch[1]->val); }
int mid() { return (l + r) >> 1; }
}*root, *tail, pool[maxn << 2];
void build(node *&o, int l, int r) {
o = new(tail++) node(l, r);
if(l == r) return;
build(o->ch[0], l, o->mid());
build(o->ch[1], o->mid() + 1, r);
}
void lazy(node *o, int pos, LL val) {
if(o->l == o->r) return (void)(o->val = val);
if(pos <= o->mid()) lazy(o->ch[0], pos, val);
else lazy(o->ch[1], pos, val);
o->upd();
}
public:
SGT() { tail = pool; }
void lazy(int pos, LL val) { lazy(root, pos, val); }
void init(int n) { build(root, 1, n); }
LL getans() { return root->val; }
int getpos() {
node *o = root;
while(o->l != o->r) o = o->ch[o->ch[0]->val <= o->ch[1]->val];
return o->l;
}
}T;
LL a[maxn], k, n, cont[maxn];
struct Tree {
Tree *ch[2];
int num;
Tree(int num = 0): num(num) { ch[0] = ch[1] = NULL; }
}*root[maxn], pool[maxn << 6], *tail;
void add(Tree *&o, Tree *lst, int dep, LL val) {
o = new(tail++) Tree(), *o = *lst, o->num++;
if(!(~dep)) return;
if(val & (1LL << dep)) add(o->ch[1], lst->ch[1], dep - 1, val);
else add(o->ch[0], lst->ch[0], dep - 1, val);
}
LL getkth(Tree *o, int dep, LL val, int nowk) {
if(dep == -1) return 0;
int now = val & (1LL << dep)? 1 : 0;
if(nowk <= o->ch[now ^ 1]->num) return getkth(o->ch[now ^ 1], dep - 1, val, nowk) | (1LL << dep);
else return getkth(o->ch[now], dep - 1, val, nowk - o->ch[now ^ 1]->num);
}
void init() {
tail = pool;
root[0] = new(tail++) Tree();
root[0]->ch[0] = root[0]->ch[1] = root[0];
}
signed main() {
n = in(), k = in();
T.init(n);
for(int i = 1; i <= n; i++) a[i] = a[i - 1] ^ in();
init();
for(int i = 1; i <= n; i++) add(root[i], root[i - 1], 31, a[i - 1]);
for(int i = 1; i <= n; i++) T.lazy(i, getkth(root[i], 31, a[i], ++cont[i]));
LL ans = 0;
while(k --> 0) {
LL now = T.getans();
ans += now;
int nowpos = T.getpos();
T.lazy(nowpos, getkth(root[nowpos], 31, a[nowpos], ++cont[nowpos]));
}
printf("%lld
", ans);
return 0;
}