这题果然是原题[BZOJ 3689 异或之].看了BZOJ原题题解,发现自己sb了,直接每个位置维护一个值保存找到了以这个位置为右端点的第几大,初始全部都是1,把每个位置作为右端点能够异或出来的最大值放入优先队列,然后找最大的一个累计答案后pop掉,假设找到的右端点是r,就把r能异或出来的第二大再加入队列.找k次就行了.这样在trie上找第k大就维护一个size就行了.mdzz这么显然居然没有想出来,还是自己太菜…

签到题没做来…

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);

}

巴特西

BZOJ 5495: [2019省队联测]异或粽子 (trie树)

CODE

最新文章

热门文章