题目链接：LOJ 3048

小粽是一个喜欢吃粽子的好孩子。今天她在家里自己做起了粽子。

小粽面前有 $n$ 种互不相同的粽子馅儿，小粽将它们摆放为了一排，并从左至右编号为 $1$ 到 $n$。第 $i$ 种馅儿具有一个非负整数的属性值 $a_i$。每种馅儿的数量都足够多，即小粽不会因为缺少原料而做不出想要的粽子。小粽准备用这些馅儿来做出 $k$ 个粽子。

小粽的做法是：选两个整数数 $l,r$，满足 $1\le l\le r\le n$，将编号在 $[l,r]$ 范围内的所有馅儿混合做成一个粽子，所得的粽子的美味度为这些粽子的属性值的异或和。

小粽想品尝不同口味的粽子，因此它不希望用同样的馅儿的集合做出一个以上的粽子。

小粽希望她做出的所有粽子的美味度之和最大。请你帮她求出这个值吧！

数据范围：$1 \le n \le 5 \times 10 ^ 5$，$1 \le k \le \min\left\{\frac{n(n - 1)}{2}, 2 \times 10 ^ 5\right\}$，$0 \le a_i \le 2 ^ {32} - 1$。

Solution

我们记 $S_i = \bigoplus_{j = 1} ^ i a_j$，那么问题转化为：找到 $k$ 对 $(l, r), l \le r$ 使得 $S_r \oplus S_{l - 1}$ 的值最大。

如果我们不考虑 $l \le r$ 的条件，问题转化为：找到 $2k$ 对有序数对，使得异或和最大。

首先，对于一个数 $S_i​$ 找到 $S_j​$ 使得 $S_i \oplus S_j​$ 最大，这个问题是平凡的，只需要建立一棵 $\text{01-Trie}​$ 树，在树上贪心寻找即可。

由于 $(l, r)$ 不可重复，于是我们必然需要支持如下操作：对于 $S_i$ 找到 $S_j$ 使得 $S_i \oplus S_j$ 为所有异或和中第 $k$ 大的。我们在 $\text{Trie}$ 树上维护一个节点大小，然后根据限制条件 $k$ 往下寻找即可，这个过程和 $\text{Splay}$ 很相似。

对于所有的 $i​$，我们维护一个优先队列 $(i, k, v)​$ 以 $v​$ 为关键字从大到小排序，其中 $k​$ 表示当前的 $v​$ 是异或和第 $k​$ 大的。每次取出队首累加到答案中，并对这个 $i​$ 找到第 $k + 1​$ 大的异或和插入队列中。

注意将 $2k​$ 个异或和累加到答案中后，最终答案需要除以 $2​$！

时间复杂度：$\mathcal O((n + k) \log n \log w)$，其中 $w$ 为值域。

Code

#include <cstdio>
#include <cstring>
#include <queue>

const int N = 5e5 + 5;

int n, k;
unsigned int a[N], s[N];

struct Data {
    int idx, k;
    unsigned int val;
    Data(int _idx = 0, int _k = 0, int _val = 0) {
        idx = _idx, k = _k, val = _val;
    }
    bool operator<(const Data &b) const {
        return val < b.val;
    }
};

template <int N>
struct Trie {
    int idx, ch[N][2], sz[N];
    void clear(int x) {
        memset(ch[x], 0, sizeof(ch[x]));
        sz[x] = 0;
    }
    void clear() {
        clear(idx = 0);
    }
    void insert(unsigned int x) {
        int u = 0;
        for (int i = 31; i >= 0; i--) {
            sz[u]++;
            int &v = ch[u][(x >> i) & 1];
            if (!v) clear(v = ++idx);
            u = v;
        }
        sz[u]++;
    }
    unsigned int query(unsigned int x, int k) {
        int u = 0;
        unsigned int ans = 0;
        for (int i = 31; i >= 0; i--) {
            int o = (x >> i) & 1;
            if (!ch[u][o ^ 1]) {
                u = ch[u][o];
            } else if (k <= sz[ch[u][o ^ 1]]) {
                ans |= 1ULL << i;
                u = ch[u][o ^ 1];
            } else {
                k -= sz[ch[u][o ^ 1]];
                u = ch[u][o];
            }
        }
        return ans;
    }
};

Trie<32 * N> T;

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%u", &a[i]);
        s[i] = s[i - 1] ^ a[i];
    }
    for (int i = 0; i <= n; i++) T.insert(s[i]);
    std::priority_queue<Data> pq;
    for (int i = 0; i <= n; i++) {
        pq.push(Data(i, 1, T.query(s[i], 1)));
    }
    k <<= 1;
    unsigned long long ans = 0;
    for (int i = 1; i <= k; i++) {
        Data x = pq.top();
        pq.pop();
        ans += x.val;
        pq.push(Data(x.idx, x.k + 1, T.query(s[x.idx], x.k + 1)));
    }
    printf("%llu\n", ans >> 1);
    return 0;
}