P5283 [十二省联考 2019] 异或粽子
题解
考虑先进行前缀异或和,这样知道左右端点可以 O(1) 求出异或和。
由于 [1,n] 内总共可以配对出 2n(n−1) 对,显然我们不能全部塞进大根堆里,取出前 k 个。
考虑对于每个 r∈[1,n],我们找到它对应的最大值,将其放进堆中,并记录其对应的右端点 r 和 l 可以选择的区间。
举个例子,初始时我们选出 r 的最优 l−1 在 [0,r) 中,将其放进堆即可。
注意:在堆中取出的 l 选择范围并不总是从 0 开始。
然后,我们开始取出堆顶,假设其左端点选择范围为 [L,R],我们应该放入左端点范围为 [L,l−1] 和 [l+1,R] 的两个最大值。
做完了。
代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;
typedef unsigned int uint;
typedef unsigned long long uLL;
struct Node {
uint d;
int l , r , L , R;
bool operator< (const Node &W) const {
return d < W.d;
}
};
const int N = 5e5+10 , M = N*33+10;
int n , k;
uint a[N];
int tr[M][2] , late[M] , idx;
int root[N];
priority_queue<Node> q;
void insert(int u , int v , int k , int pos) {
if(k < 0) {
late[v] = pos;
return;
}
int t = (a[pos] >> k) & 1;
if(u) tr[v][t^1] = tr[u][t^1];
tr[v][t] = ++ idx;
insert(tr[u][t] , tr[v][t] , k-1 , pos);
late[v] = max(late[tr[v][0]] , late[tr[v][1]]);
}
int query(int u , int minl , uint x , int k) {
if(k < 0) return late[u];
int t = (x >> k) & 1;
if(late[tr[u][t^1]] >= minl) return query(tr[u][t^1] , minl , x , k-1);
return query(tr[u][t] , minl , x , k-1);
}
int main() {
scanf("%d%d" , &n , &k);
late[0] = -1; root[0] = ++ idx;
insert(0 , root[0] , 31 , 0);
for(int i = 1 ; i <= n ; i ++) {
scanf("%u" , &a[i]);
a[i] ^= a[i-1]; root[i] = ++ idx;
insert(root[i-1] , root[i] , 31 , i);
int l = query(root[i-1] , 0 , a[i] , 31);
q.push({a[i]^a[l] , l , i , 0 , i-1});
}
uLL ans = 0;
while(k --) {
Node t = q.top(); q.pop();
ans += t.d;
if(t.l+1 <= t.R) {
int l = query(root[t.R] , t.l+1 , a[t.r] , 31);
q.push({a[t.r]^a[l] , l , t.r , t.l+1 , t.R});
}
if(t.L <= t.l-1) {
int l = query(root[t.l-1] , t.L , a[t.r] , 31);
q.push({a[t.r]^a[l] , l , t.r , t.L , t.l-1});
}
}
printf("%llu\n" , ans);
return 0;
}