BZOJ 5495
题意：求异或和前$k$大的区间的和。
类似超级钢琴做法，见bzoj 5495
那题查询最大值用的st表，这里是异或区间最大所以想到可持久化01Trie维护即可。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int MAXN = 500000 + 5, LEN = 34;
int n, k;
LL a[MAXN], s[MAXN];
int rt[MAXN], ch[MAXN * 40][2], end[MAXN * 40], sz;
int gg[40], hh[40];
struct data {
int l, r, x, y;
bool operator < (const data &rhs) const {
return (s[r] ^ s[l - 1]) < (s[rhs.r] ^ s[rhs.l - 1]);
}
};
priority_queue<data > q;
void fj(LL v) {
int len = 0; LL tmp = v; ms(gg, 0);
do {gg[++len] = tmp & 1, tmp >>= 1;} while (tmp);
}
void ins(int pre, int now, int i, int ith) {
if (i == 0) {end[now] = ith; return ;}
int c = gg[i];
ch[now][c] = ++sz, ch[now][c ^ 1] = ch[pre][c ^ 1];
ins(ch[pre][c], ch[now][c], i - 1, ith);
end[now] = max(max(end[now], end[ch[now][0]]), end[ch[now][1]]);
}
int query(int now, int l) {
for (int i = LEN; i; --i) {
int c = gg[i];
if (end[ch[now][c ^ 1]] >= l && ch[now][c ^ 1]) {
hh[i] = 1, now = ch[now][c ^ 1];
} else hh[i] = 0, now = ch[now][c];
}
return end[now];
}
void clean() {
sz = 0, ms(rt, 0), ms(ch, 0), ms(end, 0);
}
int solve() {
clean();
cin >> n >> k;
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
s[i] = s[i - 1] ^ a[i];
fj(s[i]), ins(rt[i - 1], rt[i] = ++sz, LEN, i);
}
for (int l = 1; l <= n; ++l) {
fj(s[l - 1]);
int id = query(rt[n], l);
LL bs = 1, res = 0;
for (int i = 1; i <= LEN; ++i) res += bs * hh[i], bs *= 2ll;
q.push((data){l, id, l, n});
}
LL ans = 0;
for (int i = 1; i <= k; ++i) {
data p = q.top(); q.pop();
ans += (s[p.l - 1] ^ s[p.r]);
if (p.x <= p.r - 1) {
fj(s[p.l - 1]);
int id = query(rt[p.r - 1], p.x);
LL bs = 1, res = 0;
for (int j = 1; j <= LEN; ++j) res += bs * hh[j], bs *= 2ll;
q.push((data){p.l, id, p.x, p.r - 1});
}
if (p.r + 1 <= p.y) {
fj(s[p.l - 1]);
int id = query(rt[p.y], p.r + 1);
LL bs = 1, res = 0;
for (int j = 1; j <= LEN; ++j) res += bs * hh[j], bs *= 2ll;
q.push((data){p.l, id, p.r + 1, p.y});
}
}
cout << ans;
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
/*
5 3
5 4 2 3 1
*/
