题解 P5283 【[十二省联考2019]异或粽子】
GKxx
2019-04-06 22:45:00
好吧，其实是个套路题。
这种选k大的，有一种套路就是用堆维护，连续取k个，一边取一边加入新的。跟那个给你几个数组求k大和的很像。
考虑暴力：首先$s_i$为异或前缀和这大家肯定都会，$O(n^2)$枚举区间，加进堆里或者放数组里最后排序，取前$k$大即可。
我们考虑一个优化：我们在枚举区间$[l,r]$这一步，可以只枚举一个右端点$r$，然后在$[0,r-1]$上找到一个与$s_r$异或值最大的$s_l$，那么$s_l\ xor\ s_r$即为$[1,r]$上的最大异或和（第$1$大异或和）。这样我们就把$n$个前缀最大异或和加进了堆里。
然后我们从堆中连续取$k$次，当取出一个元素时，首先把它加入答案，然后假设它是所在前缀的第$rank$大异或和，我们只要查询那个前缀的第$rank+1$大异或和，加入堆里即可。
不难发现我们需要用堆维护三元组$(pos, rank, so)$，分别表示所在前缀，第几大，异或和是多少。
剩下的问题就是，查询一个前缀的$K$大异或和，这就是可持久化01Trie模板题了。
**代码千万条，long long第一条。忘记开long long，爆零两行泪。**
```cpp
#include <cctype>
#include <cstdio>
#include <climits>
#include <algorithm>
#include <queue>
#include <vector>
template <typename T> inline void read(T& x) {
int f = 0, c = getchar(); x = 0;
while (!isdigit(c)) f |= c == '-', c = getchar();
while (isdigit(c)) x = x * 10 + c - 48, c = getchar();
if (f) x = -x;
}
template <typename T, typename... Args>
inline void read(T& x, Args&... args) {
read(x); read(args...);
}
template <typename T> void write(T x) {
if (x < 0) x = -x, putchar('-');
if (x > 9) write(x / 10);
putchar(x % 10 + 48);
}
template <typename T> inline void writeln(T x) { write(x); puts(""); }
template <typename T> inline bool chkmin(T& x, const T& y) { return y < x ? (x = y, true) : false; }
template <typename T> inline bool chkmax(T& x, const T& y) { return x < y ? (x = y, true) : false; }
typedef long long LL;
const int maxn = 5e5 + 207;
struct HeapNode {
int pos, rk;
LL so;
HeapNode() : pos(0), rk(0), so(0) {}
HeapNode(int a, int b, LL c) : pos(a), rk(b), so(c) {}
};
inline bool operator<(const HeapNode &lhs, const HeapNode &rhs) {
return lhs.so < rhs.so;
}
std::priority_queue<HeapNode> heap;
LL a[maxn], s[maxn];
int n, K;
struct Node {
int ch[2], sum;
};
Node T[maxn << 6];
int root[maxn], tot;
void insert(int &o, LL x, int i) {
T[++tot] = T[o]; ++T[o = tot].sum;
if (i < 0) return;
int j = (x >> i) & 1;
insert(T[o].ch[j], x, i - 1);
}
LL query(int o, LL x, int k, int i) {
if (i < 0) return 0;
int j = (x >> i) & 1;
int s = T[T[o].ch[j ^ 1]].sum;
if (k <= s) return (1ll << i) + query(T[o].ch[j ^ 1], x, k, i - 1);
else return query(T[o].ch[j], x, k - s, i - 1);
}
int main() {
read(n, K);
for (int i = 1; i <= n; ++i) {
read(a[i]);
s[i] = s[i - 1] ^ a[i];
insert(root[i] = root[i - 1], s[i - 1], 32);
}
for (int i = 1; i <= n; ++i)
heap.emplace(i, 1, query(root[i], s[i], 1, 32));
LL ans = 0;
for (int i = 1; i <= K; ++i) {
auto one = heap.top(); heap.pop();
ans += one.so;
if (one.rk <= one.pos)
heap.emplace(one.pos, one.rk + 1, query(root[one.pos], s[one.pos], one.rk + 1, 32));
}
writeln(ans);
return 0;
}
```
我也不知道为什么我写的这么慢，开了O2才过。幸好比赛的时候的确开O2。可是这跟我有什么关系呢...我又没在考场上做出来
数组不要开小