解题思路：区间的的异或和我们利用前缀异或来处理 这道题和超级钢琴十分类似，只是转化成立异或，我们可以利用Tire来解决问题，因为要多次询问区间第K大异或，我们利用可持久化Trie来维护前缀异或和。我们固定区间的右端点，把每个每个区间的异或最大值放于堆中去维护，每当我们取出一个数后，我们往堆里面放入下一个异或最大值。类似再Trie树上询问区间第K大异或。代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 5e5 + 5; int n, k; ll pre[maxn], x; struct node { int ls, rs, cnt0, cnt1; ///ls为0 ，rs为1 } p[maxn * 80]; int root[maxn], times; struct state { int pos, k; ll maxn; bool friend operator<(state a, state b) { return a.maxn < b.maxn; } } temp; void insert(int &now, int old, int pos, ll x) { if (pos == -1) return; now = ++times; p[now] = p[old]; if (x >> pos & 1) { p[now].cnt1++; insert(p[now].rs, p[old].rs, pos - 1, x); } else { p[now].cnt0++; insert(p[now].ls, p[old].ls, pos - 1, x); } } ll query(int now, int pos, ll x, int k) { ///Trie 上询问第K大异或 if (pos == -1) return 0; if (x >> pos & 1) { if (k <= p[now].cnt0) return query(p[now].ls, pos - 1, x, k); else return query(p[now].rs, pos - 1, x, k - p[now].cnt0) + (1LL << pos); } else { if (k <= p[now].cnt1) return (1LL << pos) + query(p[now].rs, pos - 1, x, k); else return query(p[now].ls, pos - 1, x, k - p[now].cnt1); } } int main() { ll ans = 0; scanf("%d %d", &n, &k); insert(root[0], root[0], 34, 0); for (int i = 1; i <= n; i++) { scanf("%lld", &x); pre[i] = pre[i - 1] ^ x; insert(root[i], root[i - 1], 34, pre[i]); } priority_queue<state> q; for (int i = 1; i <= n; i++) { temp.pos = i, temp.k = 1; temp.maxn = pre[i] ^ query(root[i - 1], 34, pre[i], 1); q.push(temp); } while (k--) { temp = q.top(), q.pop(); ans += temp.maxn; if (temp.pos == temp.k) continue; temp.maxn = pre[temp.pos] ^ query(root[temp.pos], 34, pre[temp.pos], ++temp.k); q.push(temp); } printf("%lld\n", ans); }
