# BZOJ 5495: [2019 provincial team joint test] XOR zongzi (trie tree)

This question is indeed the original one [BZOJ 3689 XOR] After looking at the original problem solution of BZOJ, I found that I have sb. I directly maintained a value for each location and found the largest number of right endpoints with this location as the right endpoint. Initially, all of them were 1. I put each location as the largest value that can be XOR out of the right endpoint into the priority queue, and then I found the largest cumulative answer and pop it out. Assuming that the right endpoint is r, I added the second largest value that can be XOR out Queue. Just look for K times. In this way, it's OK to find the k-th largest in trie and maintain a size. mdzz obviously didn't come up with it, but it's still too delicious

The check-in question didn't come up

# CODE

```#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
char cb[1<<15],*cs=cb,*ct=cb;
template<class T>inline void read(T &res) {
char ch; while(!isdigit(ch=getchar()));
for(res=ch-'0';isdigit(ch=getchar());res=res*10+ch-'0');
}
const int MAXN = 500005;
const int MAXM = MAXN*32;
struct node {
int id; LL val;
node(){}
node(int ii, LL vv):id(ii), val(vv){}
bool operator <(const node &o)const {
return val < o.val;
}
};
priority_queue<node> q;
int ch[MAXM], sz[MAXM], cnt[MAXM], tot;

int n, k, now[MAXN];
LL s[MAXN];

inline void insert(LL x) {
int r = 0;
for(int i = 31, c; ~i; --i) {
c = (x & (1ll<<i)) ? 1 : 0;
if(!ch[r][c]) ch[r][c] = ++tot;
++sz[r = ch[r][c]];
}
++cnt[r];
}

inline LL kth(LL x, int k) {
int r = 0; LL re = 0;
for(int i = 31, c; ~i; --i) {
c = (x & (1ll<<i)) ? 0 : 1;
if(sz[ch[r][c]] < k) k -= sz[ch[r][c]], r = ch[r][!c];
else re ^= 1ll<<i, r = ch[r][c];
}
return re;
}

int main () {
insert(0);
for(int i = 1, x; i <= n; ++i)
read(x), s[i] = s[i-1] ^ x, insert(s[i]);
for(int i = 0; i <= n; ++i)
q.push(node(i, kth(s[i], ++now[i])));
LL ans = 0;
while(k--) {
node u = q.top(); q.pop();
if(k&1) ans += u.val;
if(now[u.id] < n) q.push(node(u.id, kth(s[u.id], ++now[u.id])));
}
printf("%lld\n", ans);
}
```

Posted on Thu, 28 Nov 2019 10:29:20 -0800 by cavemaneca