题目链接
题目大意
让你求区间异或和前\(k\)大的异或和的和。
正解
这道题目是Blue sky大佬教我做的（祝贺bluesky大佬进HA省A队）
我们做过某一些题目，非常的相似。还有还有 感觉这一些题目拼在一起就变成了这一道水题。 首先我们需要预处理出，所有区间的异或最大值。 这个东西可以用可持久化\(01trie\)实现，那么我们思考一下如何实现查询第\(k\)大的值的操作。以下是关于01字典树中查询第k大的操作的讲解
可以参考平衡树和01trie贪心的策略。
因为我们是找到当前的子节点的另外一个。 因为从高位开始贪心，所以如果不相同则一定是比我们要求的答案要大，那么就减去这一部分，并且调到另外一个儿子上。 代码实现ll query(int rt, ll val, int kth, int len) { ll res = 0; for (int i = len; ~i; i --) { int p = (val >> i) & 1; if (cnt[ch[rt][p ^ 1]] < kth) kth -= cnt[ch[rt][p ^ 1]], rt = ch[rt][p]; else res += (1ll << i), rt = ch[rt][p ^ 1]; } return res;} 那么维护以每一个节点为结束的区间异或最大值。
那么回归正题，参照最小函数值和超级钢琴的思路，我们就每一次取出最大值之后，将这个区间次大值拎出来，放入优先队列中。
运行k遍就是我们需要的答案了。#include#define ms(a, b) memset(a, b, sizeof(a))#define ll long long#define ull unsigned long long#define ms(a, b) memset(a, b, sizeof(a))#define inf 0x3f3f3f3f#define db double#define Pi acos(-1)#define eps 1e-8#define N 600005using namespace std;template T power(T x, T y, T mod) { x %= mod; T res = 1; for (; y; y >>= 1) { if (y & 1) res = (res * x) % mod; x = (x * x) % mod; } return res; }template void read(T &x) { x = 0; T fl = 1; char ch = 0; for (; ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') fl = -1; for (; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48); x *= fl;}template void write(T x) { if (x < 0) x = -x, putchar('-'); if (x > 9) write(x / 10); putchar(x % 10 + '0');}template void writeln(T x) { write(x); puts(""); }struct node { ll val; int id; node(ll Val = 0, int Id = 0) { val = Val; id = Id; } bool operator < (const node &B) const { return val < B.val; }};priority_queue q;struct L_Trie { int ch[N * 40][2], cnt[N * 40], tot; void ins(int &rt, int pre, ll val, int len) { rt = ++ tot; int k = rt; for (int i = len; ~i; i --) { ch[k][0] = ch[pre][0]; ch[k][1] = ch[pre][1]; cnt[k] = cnt[pre] + 1; int p = (val >> i) & 1; ch[k][p] = ++ tot; k = ch[k][p]; pre = ch[pre][p]; } cnt[k] = cnt[pre] + 1; } ll query(int rt, ll val, int kth, int len) { ll res = 0; for (int i = len; ~i; i --) { int p = (val >> i) & 1; if (cnt[ch[rt][p ^ 1]] < kth) kth -= cnt[ch[rt][p ^ 1]], rt = ch[rt][p]; else res += (1ll << i), rt = ch[rt][p ^ 1]; } return res; }} trie;int root[N], kth[N];ll sumxor[N], a[N];int n, k;ll ans;int main() { read(n); read(k); trie.ins(root[0], 0, 0, 31); for (int i = 1; i <= n; i ++) { kth[i] = 1; read(a[i]); sumxor[i] = sumxor[i - 1] ^ a[i]; trie.ins(root[i], root[i - 1], sumxor[i], 31); q.push(node(trie.query(root[i - 1], sumxor[i], kth[i], 31), i)); } while (k --) { node cur = q.top(); q.pop(); ans += cur.val; kth[cur.id] ++; q.push(node(trie.query(root[cur.id - 1], sumxor[cur.id], kth[cur.id], 31), cur.id)); } printf("%lld\n", ans); return 0;}