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;
#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()));
    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][2], 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 () {
    read(n), read(k), k<<=1;
    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