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


#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
char cb[1<<15],*cs=cb,*ct=cb;
#define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<15,stdin),cs==ct)?0:*cs++)
template<class T>inline void read(T &res) {
    char ch; while(!isdigit(ch=getchar()));
const int MAXN = 500005;
const int MAXM = MAXN*32;
struct node {
    int id; LL val;
    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][2], sz[MAXM], cnt[MAXM], tot;
int n, k, now[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]]; 
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 () {
    read(n), read(k), k<<=1;
    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.pop();
        if(k&1) ans += u.val;
        if(now[] < n) q.push(node(, kth(s[], ++now[])));
    printf("%lld\n", ans);

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