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

xht · 2019-04-11 00:20:10 · 题解

题目地址：P5283 [十二省联考2019]异或粽子

题意

前 k 大区间异或和。

思路

一个很基础的转化是，我们可以 O(n) 求出前缀异或和 s_0, s_1, ..., s_n 。

那么显然 xor_{i=l}^{r} = s_{l-1}\ xor\ s_r 。

题意转化为，在 s_0, s_1, ..., s_n 这 n+1 个数中，选出 k 对 (s_i, s_j)(i<j) ，使每对的异或值的和最大。

暴力分

注意到有 60 分的数据满足 n \leq 1000 ，而上述所说的数对一共有 O(n^2) 个。

那么我们可以把每一对的异或值都插入一个大根堆（优先队列）中，然后弹出 k 次最大值，弹出的所有值的和就是最终答案。

#include <bits/stdc++.h>
#define ui unsigned int
#define ull unsigned long long
using namespace std;
const int N = 5e5 + 6;
int n, k;
ui a[N], s[N];
priority_queue<ui> q;
ull ans;

inline ui rd() {
    ui x = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x;
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) a[i] = rd(), s[i] = s[i-1] ^ a[i];
    for (int l = 1; l <= n; l++)
        for (int r = l; r <= n; r++)
            q.push(s[r] ^ s[l-1]);
    while (k--) ans += q.top(), q.pop();
    cout << ans << endl;
    return 0;
}

注意：由于这道题 a 数组的数据范围为 0 \leq ai \leq 4294967295 ，所以要开unsigned int（当然long long也行）。

正解

前置芝士

可持久化Trie

~~洛谷似乎并没有可持久化Trie的模板2333。~~

首先你要知道可持久化。

其次你要会Trie，并且要会这道题所要使用的01Trie。

如果这两者都会了，那么请先去把P4735 最大异或和A掉。

A掉这道题之后，你就应该知道如何求在序列 a 的一个给定区间 [l, r] 中选择一个数 i 使 a_i 与另一个给定的值异或起来最大。

简要的思路是，建立可持久化Trie，在给定区间的Trie上贪心的优先选择与给定值当前位相反的节点（指针）。

本题思路

一开始，对于每个右端点 r ，在前缀异或和序列 s 的区间 [0,r-1] 选择一个左端点 l 使 s_l 与 s_r 异或起来最大，并将描述这个值的所有信息以这个值为关键字插入一个大根堆中。

描述这个值所需要的信息有：

这个值的大小；
这个值左端点的选择区间；
这个值的左右端点。

可以用一个结构体记录，也可以用若干个pair记录，我的代码实现中是用的后者。

仍然弹出 k 次堆中的最大值，那么弹出的所有值的和就是最终答案。

但是在弹出的同时也在不断的插入。

假设此时弹出来值及其描述信息为：

这个值为 x ；
这个值左端点的选择区间为 [L,R]；
这个值的左右端点为 l,r。

首先将 x 加入答案。

然后将选择区间以 l 为界限分成两段 [L,l-1], [l+1,R] ，分别在这两个区间中选择与 s_r 最大的异或值，将这个值及其描述信息插入大根堆中。

正确性

~~不言而喻。~~

本题代码实现比较复杂，细节比较多，我的代码仅供参考，建议自己清楚思路后独立AC。

#include <bits/stdc++.h>
#define ui unsigned int
#define ull unsigned long long
#define pii pair<int, int>
#define X first
#define Y second
#define mp make_pair
using namespace std;
const int N = 5e5 + 6;
int n, m, trie[N<<6][2], late[N<<6], rt[N], t;
ui a[N];
ull ans;
priority_queue<pair<ui, pair<pii, pii> > > q;

inline ui rd() {
    ui x = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9')
        x = x * 10 + (ch - '0'), ch = getchar();
    return x;
}

void ins(int i, int k, int p, int o) {
    if (k < 0) return late[o] = i, void();
    int c = (a[i] >> k) & 1;
    if (p) trie[o][c^1] = trie[p][c^1];
    trie[o][c] = ++t;
    ins(i, k - 1, trie[p][c], trie[o][c]);
    late[o] = max(late[trie[o][0]], late[trie[o][1]]);
}

int ask(ui x, int k, int o, int p) {
    if (k < 0) return late[o];
    int c = (x >> k) & 1;
    return ask(x, k - 1, trie[o][c^(late[trie[o][c^1]]>=p)], p);
}

int main() {
    cin >> n >> m;
    late[0] = -1;
    ins(0, 31, 0, rt[0] = ++t);
    for (int i = 1; i <= n; i++) {
        a[i] = rd() ^ a[i-1];
        ins(i, 31, rt[i-1], rt[i] = ++t);
        int j = ask(a[i], 31, rt[i-1], 0);
        q.push(mp(a[j] ^ a[i], mp(mp(0, i - 1), mp(j, i))));
    }
    while (m--) {
        ans += q.top().X;
        int l = q.top().Y.Y.X, i = q.top().Y.Y.Y;
        pii k = q.top().Y.X;
        q.pop();
        if (l != k.Y) {
            int j = ask(a[i], 31, rt[k.Y], l + 1);
            q.push(mp(a[j] ^ a[i], mp(mp(l + 1, k.Y), mp(j, i))));
        }
        if (l != k.X) {
            int j = ask(a[i], 31, rt[l-1], k.X);
            q.push(mp(a[j] ^ a[i], mp(mp(k.X, l - 1), mp(j, i))));
        }
    }
    cout << ans << endl;
    return 0;
}