P5283 [十二省联考 2019] 异或粽子
大意
求前 \(k\) 大的互不相同的异或和。
思路
首先，我们将其转换一下，求出前缀异或和，\(s\)，$s_i = s_i \oplus s_{i - 1} $，这样，对于区间 \([l, r]\) 的异或和询问就变成了 \(s_r \oplus s_{l - 1}\)。
知道了这个之后，我们的问题现在转化为了，在这 \(n\) 个 \(s\) 里面选择 \(k\) 对，使得其和最大，这个时候，我们要处理的问题是对于 \(s_i\) 来说，如何找到一个 \(s_j\)，使得其 \(s_i \oplus s_j\) 的值最大。这个问题十分经典（但是我也刚知道），可以用 Trie 来处理这种动态找最大异或和的问题。
那么如何在 Trie 上维护这个东西呢？我们考虑将每个 \(s_i\) 插入 Trie 里面，那么记录每个节点经过的点的个数，我们一定是希望走 \(op \oplus 1\) 的位置的，但是如果没有 \(op \oplus 1\) 这个位置，就走不了，且，若是左子树的大小不够，也走不了，必须走到 \(sz \ge rk\) 的地方，这个才是对的。于是就类似权值线段树静态查第 \(k\) 大差不多，不过此题我们要处理的是前 \(2k\) 大，因为我们忽略了 \(l \le r\) 的限制。
我们只需要用一个大根堆记录即可，但是每个答案都会以 \(s_i\) 和 \(s_j\) 为基准分别各出现一次，那么最终我们选择的答案需要除以 \(2\)。
代码
#include<iostream>
#include<queue>
using namespace std;#define ll long long
const int MAXN = 5e5 + 5;
const int MAXT = MAXN * 32;int ch[MAXT][2], cnt[MAXT];
ll s[MAXN], tot = 0, n, k;struct node{int id, rk;ll val;bool operator<(const node &other)const{return val < other.val;}
};void Insert(ll x){int now = 0;for(int i = 31;i >= 0;i --){int op = (x >> i) & 1;if(!ch[now][op]) ch[now][op] = ++ tot;now = ch[now][op];cnt[now] ++;}
}ll query(ll x, int rk){int now = 0;ll res = 0;for(int i = 31;i >= 0;i --){int op = (x >> i) & 1;op ^= 1;if(!ch[now][op]){now = ch[now][op ^ 1];}else if(rk <= cnt[ch[now][op]]){res |= (1LL << i);now = ch[now][op];}else{rk -= cnt[ch[now][op]];now = ch[now][op ^ 1];}}return res;
}int main(){cin.tie(0) -> ios::sync_with_stdio(0);cin >> n >> k;s[0] = 0;Insert(s[0]);for(int i = 1;i <= n;i ++){ll a; cin >> a;s[i] = s[i - 1] ^ a;Insert(s[i]);}priority_queue<node> q;for(int i = 0;i <= n;i ++){ll x = query(s[i], 1);q.push({i, 1, x});}ll ans = 0;for(int i = 1;i <= 2 * k;i ++){node t = q.top();ans += t.val;q.pop();if(t.rk < n){q.push({t.id, t.rk + 1, query(s[t.id], t.rk + 1)});}}cout << ans / 2;return 0;
}