[十二省联考2019]异或粽子

跟超级钢琴做法差不多， 就是 [l,r] 中的最大值的位置是 k， 那么次大值的位置必定在 [l,k-1] 和 [k+1,r] 其中之一的思想。

#include <bits/stdc++.h>
typedef long long LL;
using namespace std;

const int N = 5e5, K = 2e5;

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

int n, k; // 1 << 31
LL A[N + 233];
struct Trie { int c[2], col; Trie() {c[0]=c[1]=col=0;} } a[N * 34 + 2333];
int tot, root[N + 233];

void init() {
	int p = root[0] = ++ tot;
	for (int i = 31; ~ i; -- i) a[p].c[0] = ++ tot, p = tot;
}

void ins (int id, LL x) {
	int p = root[id - 1], q = root[id] = ++ tot;
	a[q].col = id;
	for (int i = 31; ~ i; -- i) {
		int v = (x >> i) & 1;
		a[a[q].c[v] = ++ tot].col = id;
		a[q].c[v ^ 1] = a[p].c[v ^ 1];
		p = a[p].c[v], q = tot;
	}
}

pair<LL,int> ask (int l, int r, LL x) {
	LL res = 0ll;
	int p = root[r];
	for (int i = 31; ~ i; -- i) {
		int v = (x >> i) & 1;
		if (a[p].c[v ^ 1] && a[a[p].c[v ^ 1]].col >= l)
			res += (1ll << i), p = a[p].c[v ^ 1];
		else
			p = a[p].c[v];
	}
	return make_pair (res, a[p].col);
}

struct sta {	int l, r, x; LL v; int pos; sta (int a, int b, int c, LL d, int e) : l(a), r(b), x(c), v(d), pos(e) {} sta() {}
 } q[N*2+23];
bool operator < (sta s1, sta s2) { return s1.v < s2.v; }
int tp;


int main()
{
	init();
	n = rd(), k = rd();
	for (int i = 1; i <= n; ++ i) A[i] = A[i - 1] ^ rd(), ins (i, A[i]);
	for (int i = 1; i <= n; ++ i) {
		pair<LL,int> tmp = ask (0, i - 1, A[i]);
		q[++ tp] = sta (0, i - 1, i, tmp.first, tmp.second);
		push_heap (q + 1, q + 1 + tp);
	}
	LL ans = 0ll;
	for (int i = 1; i <= k; ++ i) {
		sta now = q[1];
		pop_heap (q + 1, q + 1 + tp);
		-- tp;
		ans += now.v;
		int x = now.x, l = now.l, r = now.r, k = now.pos;
		if (l < k) {
			pair<LL,int> tmp = ask (l, k - 1, A[x]);
			q[++ tp] = sta (l, k - 1, x, tmp.first, tmp.second);
			push_heap (q + 1, q + tp + 1);
		}
		if (k < r) {
			pair<LL,int> tmp = ask (k + 1, r, A[x]);
			q[++ tp] = sta (k + 1, r, x, tmp.first, tmp.second);
			push_heap (q + 1, q + tp + 1);
		}
	}
	cout << ans;
	return 0;
}