洛谷P5283 [十二省联考 2019] 异或粽子题解

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

题意：

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

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

小粽的做法是：选两个整数数 \(l\), \(r\)，满足 \(1 \le l \le r \le n\)，将编号在 \([l, r]\) 范围内的所有馅儿混合做成一个粽子，所得的粽子的美味度为这些粽子的属性值的异或和。（异或就是我们常说的 xor 运算，即 C/C++ 中的 ˆ 运算符或 Pascal 中的 xor 运算符）

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

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

输入格式：

第一行两个正整数 \(n\), \(k\)，表示馅儿的数量，以及小粽打算做出的粽子的数量。

接下来一行为 \(n\) 个非负整数，第 \(i\) 个数为 \(a_i\)，表示第 \(i\) 个粽子的属性值。

输出格式：

输出一行一个整数，表示小粽可以做出的粽子的美味度之和的最大值。

数据范围：

\(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\) 。

明天端午节，写个和粽子有关的题。好吧其实这道题和粽子没什么关系。

就像这道题和什么可持久化 Trie 没关系一样（~~就算有关我也不会~~）

按照套路，我们对原数组做一遍前缀异或和，那么就是找到异或值最大的 \(k\) 对 \(i,j\) 满足 \(0 \le i < j \le n\) 。

最令人头疼的就是这个 \(i,j\) 需要满足 \(i < j\) ，否则我们可以直接用下面的算法求出答案：

将 \(0\) 到 \(n\) 的所有前缀异或和的最大匹配塞入优先队列。（最大匹配指使得他们异或值最大的另一个位置）
每次取出队首元素，然后将第二大的匹配塞入优先队列，这个过程类似于平衡树的操作。
重复以上过程，直到不能再取。由于 \(i,i\) 的答案一定为 \(0\) ，所以这个算法只会多算 \(i>j\) 的情况。
注意步骤二中不一定是第二大匹配（只是为了方便描述），设队首是第 \(x\) 大，那就是 \(x+1\) 大的匹配。

然后我们发现，不限制 \(i,j\) 的话，最优方案一定会尽可能把 \(i,j\) 和 \(j,i\) 都取到。

那么我们完全可以直接取 \(2k\) 个，然后把答案除以 \(2\) 。

时间复杂度 \(\mathcal{O}(n \log V + n \log n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define N ((int)(5e5 + 15))

struct node { int id, rk; ll v; };
bool operator<(node a, node b) { return a.v < b.v; }
priority_queue<node> q; ll res = 0, a[N];
int tot, sz[N * 20], tr[N * 20][2];
void insert(ll x)
{
    int u = 0;
    for(int i = 35; ~i; i--)
    {
        int c = (x >> i) & 1; ++sz[u];
        if(!tr[u][c]) { tr[u][c] = ++tot; } u = tr[u][c];
    }
    ++sz[u];
}
ll query(ll x, int rk)
{
    int u = 0; ll sum = 0;
    for(int i = 35; ~i; i--)
    {
        int c = (x >> i) & 1;
        if(!tr[u][c ^ 1]) u = tr[u][c];
        else {
            if(rk <= sz[tr[u][c ^ 1]]) {
                u = tr[u][c ^ 1], sum |= 1ll << i;
            } else { rk -= sz[tr[u][c ^ 1]], u = tr[u][c]; }
        }
    }
    return sum;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n, m; cin >> n >> m; insert(0);
    for(int i = 1; i <= n; i++) { cin >> a[i], a[i] ^= a[i - 1]; insert(a[i]); }
    for(int i = 0; i <= n; i++) q.push({i, 1, query(a[i], 1)});
    for(int i = 1; i <= 2 * m; i++)
    {
        auto t = q.top(); q.pop(); res += t.v;
        if(t.rk < n) q.push({t.id, t.rk + 1, query(a[t.id], t.rk + 1)});
    }
    cout << res / 2 << '\n';
    return 0;
}