P5283异或粽子是什么编程题？
摘要：P5283 [十二省联考 2019] 异或粽子 大意 求前 (k) 大的互不相同的异或和。 思路 首先，我们将其转换一下，求出前缀异或和，(s)，$s_i = s_i oplus s_{i - 1} $，这样，对于区间 ([l,
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;
}