大概率是 q 出了问题,不过机房几个人一起找也没招出来,本地第一组数据 AC,不过在 oj 上 re 了。
#include <iostream>
#include <queue>
#define int long long
using namespace std;
const int MAXN = 2e7 + 7;
int a[MAXN], s[MAXN], trie[MAXN][2], size[MAXN];
int n, k, ans, tot;
int _end[MAXN];
struct node
{
int x, y, w;
bool operator <(const node &a)const
{
return w < a.w;
}
};
priority_queue<node> q;
void insert(int x)
{
int u = 0;
for (int i = 31; i >= 0; i --)
{
int ch = (x >> i) & 1;
if (!trie[u][ch])
trie[u][ch] = ++ tot;
// cout << u << ' ' << ch << ' ' << trie[u][ch] << endl;
u = trie[u][ch];
size[u] ++;
}
_end[u] ++;
}
int query(int x, int t)
{
int u = 0, res = 0;
for (int i = 31; i >= 0; i --)
{
bool ch = (x >> i) & 1;
if(t <= size[trie[u][ch ^ 1]]) ch ^= 1;
else t -= size[trie[u][ch ^ 1]];
// cout << u << ' ' << ch << ' ' << trie[u][ch] << ' ' << size[trie[u][ch]] << ' ';
u = trie[u][ch];
res <<= 1, res |= ch;
// cout << res << endl;
}
return res ^ x ;
}
signed main()
{
cin >> n >> k;
for (int i = 1; i <= n; i ++)
{
cin >> a[i];
s[i] = s[i - 1] ^ a[i];
}
for (int i = 0; i <= n; i ++)
{
insert(s[i]);
}
// cout << endl;
// for (int i = 0; i <= n; i ++) cout << s[i] << ' ';
// cout << endl << endl;
// query(3, 2);
// return 0;
for (int i = 0; i <= n; i ++)
{
int w = query(s[i], 1);
q.push((node){i, 1, w});
}
// for (int i = 1; i <= n; i ++)
// {
// for (int j = 1; j < n; j ++)
// {
// cout << s[i] << ' ' << j << ' ' << query(s[i], j) << endl;;
// }
// }
// cout << endl << endl;
int ans = 0;
k *= 2;
while (k --)
{
node t = (node){1, 1, 1};
if(q.size())
{
t = q.top();
q.pop();
}
ans += t.w;
// cout << s[t.x] << ' ' << t.y << ' ' << t.w << ' ' << ans << endl;
t.y ++;
if(t.y < n)
{
t.w = query(s[t.x], t.y);
// cout << s[t.x] << ' ' << t.y << ' ' << t.w << endl;
q.push(t);
}
}
cout << ans / 2;
return 0;
}