记录编号	569861	评测结果	AAAAAAAAAAAAAAAATTTT
题目名称	[HAOI 2019]异或粽子	最终得分	80
用户昵称	代金永爱关凯文	是否通过	未通过
代码语言	C++	运行时间	15.958 s
提交时间	2022-03-17 18:54:21	内存使用	225.55 MiB

#include <bits/stdc++.h>
#define ui unsigned int
#define ull unsigned long long
#define pii pair<int, int>
#define X first
#define Y second
#define mp make_pair
using namespace std;
const int N = 5e5 + 6;
int n, m, trie[N<<6][2], late[N<<6], rt[N], t;
ui a[N];
ull ans;
priority_queue<pair<ui, pair<pii, pii> > > q;

inline ui rd() {
	ui x = 0;
	char ch = getchar();
	while (ch < '0' || ch > '9') ch = getchar();
	while (ch >= '0' && ch <= '9')
		x = x * 10 + (ch - '0'), ch = getchar();
	return x;
}

void ins(int i, int k, int p, int o) {
	if (k < 0) return late[o] = i, void();
	int c = (a[i] >> k) & 1;
	if (p) trie[o][c^1] = trie[p][c^1];
	trie[o][c] = ++t;
	ins(i, k - 1, trie[p][c], trie[o][c]);
	late[o] = max(late[trie[o][0]], late[trie[o][1]]);
}

int ask(ui x, int k, int o, int p) {
	if (k < 0) return late[o];
	int c = (x >> k) & 1;
	return ask(x, k - 1, trie[o][c^(late[trie[o][c^1]]>=p)], p);
}

int main() {
	freopen("haoi2019_xor.in","r",stdin);
	freopen("haoi2019_xor.out","w",stdout);
	cin >> n >> m;
	late[0] = -1;
	ins(0, 31, 0, rt[0] = ++t);
	for (int i = 1; i <= n; i++) {
		a[i] = rd() ^ a[i-1];
		ins(i, 31, rt[i-1], rt[i] = ++t);
		int j = ask(a[i], 31, rt[i-1], 0);
		q.push(mp(a[j] ^ a[i], mp(mp(0, i - 1), mp(j, i))));
	}
	while (m--) {
		ans += q.top().X;
		int l = q.top().Y.Y.X, i = q.top().Y.Y.Y;
		pii k = q.top().Y.X;
		q.pop();
		if (l != k.Y) {
			int j = ask(a[i], 31, rt[k.Y], l + 1);
			q.push(mp(a[j] ^ a[i], mp(mp(l + 1, k.Y), mp(j, i))));
		}
		if (l != k.X) {
			int j = ask(a[i], 31, rt[l-1], k.X);
			q.push(mp(a[j] ^ a[i], mp(mp(k.X, l - 1), mp(j, i))));
		}
	}
	cout << ans << endl;
	return 0;
}