1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
| #include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 500000 + 5;
int n, k, pre[N], a[N], root[N];
struct Node {
int r, xorans, nownum;
bool operator < (const Node &rhs) const {
return xorans < rhs.xorans;
}
};
struct Trie {
int trie[N*35][2], sz[N*35], pos = 0;
void pushup(int now) {
sz[now] = sz[trie[now][0]] + sz[trie[now][1]];
}
void Build(int& now, int x, int k) {
now = ++pos;
if(k == -1) {
sz[now]++;
return ;
}
if(!(x & (1ll << k))) Build(trie[now][0], x, k-1);
else Build(trie[now][1], x, k-1);
pushup(now);
}
void Update(int& now, int old, int x, int k) {
now = ++pos; trie[now][0] = trie[old][0], trie[now][1] = trie[old][1], sz[now] = sz[old];
if(k == -1) {
sz[now]++;
return ;
}
if(!(x & (1ll << k))) Update(trie[now][0], trie[old][0], x, k-1);
else Update(trie[now][1], trie[old][1], x, k-1);
pushup(now);
}
int XorKth(int now, int ans, int x, int k, int kth) {
if(k == -1) return ans;
if(!(x & (1ll << k))) {
int ls = sz[trie[now][0]], rs = sz[trie[now][1]];
if(kth <= ls) return XorKth(trie[now][0], ans * 2, x, k-1, kth);
else return XorKth(trie[now][1], ans * 2 + 1, x, k-1, kth - ls);
} else {
int ls = sz[trie[now][1]], rs = sz[trie[now][0]];
if(kth <= ls) return XorKth(trie[now][1], ans * 2 + 1, x, k-1, kth);
else return XorKth(trie[now][0], ans * 2, x, k-1, kth - ls);
}
}
}t;
signed main() {
scanf("%lld%lld", &n, &k);
for(int i = 1; i <= n; i++)
scanf("%lld", &a[i]), pre[i] = (pre[i-1] ^ a[i]);
t.Build(root[1], pre[0], 32);
for(int i = 2; i <= n; i++)
t.Update(root[i], root[i-1], pre[i-1], 32);
priority_queue <Node> q;
for(int i = 1; i <= n; i++) {
int xo = t.XorKth(root[i], 0, pre[i], 32, i);
q.push((Node){i, (xo ^ pre[i]), i});
}
int ans= 0;
for(int i = 1; i <= k; i++) {
Node x = q.top(); q.pop();
ans += x.xorans;
if(i == k) {
cout<<ans << endl;
return 0;
}
else {
int id = x.nownum;
--id;
if(id <= 0) continue;
int xo = t.XorKth(root[x.r], 0, pre[x.r], 32, id);
q.push((Node){x.r, (xo ^ pre[x.r]), id});
}
}
cout <<ans << endl;
return 0;
}
|