[十二省联考2019]异或粽子 01trie

链接

luogu

思路

首先求前k大的(xo[i]^xo[j])（i<j）。

考场上只想到01trie,不怎么会写可持久，就写了n个01trie，和直接sort一样、、

咳咳，官方题解是。

一个堆维护i为终点，可以取得位置为\([L,R]\)的最大值为val。

每次选最大的，然后将这个点分裂成两个:

i为终点，可以取得位置为\([L,x-1]\)的最大值为\(val_1\)。

i为终点，可以取得位置为\([x+1,R]\)的最大值为\(val_2\)。

具体咋维护，可持久01trie(他应该就是说的主席树，忘记啦)。

其实可以直接是直接记录当前应该取第几大，建立可持久化01trie

还有一种是把k*2，这样消去了大小限制，直接建立一颗01trie，在上面跑k大，最后除以2

对角线上是有重复的，但是你一定选不到呀，xor起来为0

错误

1.一个hello wrold居然跑10s，垃圾病毒防护天天扫我exe。

2.我居然不知道trie可以求第k大xor值，菜的一批、、、、

代码

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = 5e5 + 6;

ll read() {

    ll x = 0, f = 1; char s = getchar();

    for (; s > '9' || s < '0'; s = getchar()) if (s == '-') f = -1;

    for (; s >= '0' && s <= '9'; s = getchar()) x = x * 10 + s - '0';

    return x * f;

}

int n, k, cnt=1, num[N];

ll a[N];

struct node {

    int ch[2], siz;

} e[N * 35];

priority_queue<pair<ll, int> > q;

void insert(ll x) {

    int p = 1;

    for (int i = 31; i >= 0; --i) {

        bool T_T = x & (1LL << i);

        e[p].siz++;

        if (!e[p].ch[T_T])

            e[p].ch[T_T] = ++cnt;

        p = e[p].ch[T_T];

    }

    e[p].siz++;

}

ll k_th(ll x, int k) {

    if (k > n)

        return 0;

    ll ans = 0;

    int p = 1;

    for (int i = 31; i >= 0; --i) {

        bool T_T = x & (1LL << i);

        if (e[e[p].ch[T_T ^ 1]].siz >= k)

            ans = ans | (1LL << i), p = e[p].ch[T_T ^ 1];

        else

            k -= e[e[p].ch[T_T ^ 1]].siz, p = e[p].ch[T_T];

    }

    return ans;

}

int main() {

    n = read(), k = read() * 2;

    insert(0);

    for (int i = 1; i <= n; ++i) a[i] = a[i - 1] ^ read(), insert(a[i]);

    for (int i = 0; i <= n; ++i) q.push(make_pair(k_th(a[i],num[i]=1),i));

    ll ans = 0;

    while (k--) {

    	pair<ll, int> u = q.top();

    	q.pop();

        ans += u.first;

        u.first=k_th(a[u.second],++num[u.second]);

        if(num[u.second]<n) q.push(u);

    }

    cout << ans / 2 << "\n";

    return 0;

}