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

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

首先把题目转换一下，可以得到以下题面：

有一个长度为 $n$ 的序列 $a$，求两两异或的前 $K$ 大值。

本质和 CF241B Friends 一样。

$Tricks:$

补全三角形矩阵，答案 $÷2$。

考虑建立可持久化 $Trie$。之后考虑两种情况。

如果 $K$ 和 $n$ 是同阶的，我们可以得到一个 $K\log K$ 的算法。

我们维护一个大根堆，常规维护一下第 $K$ 小。之后考虑每一个位置的贡献。我们不妨考虑每一个位置作为右边位置的贡献。那么就是求左边异或第 $K$ 小。

对于每一个位置都这样做。可以保证有答案。

当取出一个元素的时候，更新答案，然后使用当前元素计算比其小 $1$ 个 $rank$ 的答案，放入堆。

可以得到复杂度是 $O((n+k)\log (nk))$。

$n$ 是插入的复杂度， $k$ 是堆的复杂度。

---

如果 $n$ 比较小，然后 $k$ 是 $n^2$ 级别的呢？

我们考虑对于所有的数都插入到 $Trie$ 里面。

发现如果可以得到第 $K$ 大的值，那么计算比其小的值可以通过 $O(n{\log }^{2}w)$ 的复杂度计算得到。

然后我们直接暴力二分加 $check$ 得到第 $K$ 大就好了。

---

所以这种问题的复杂度可以做到 $O(n\log n+min(k\log k,n{\log }^{2}w))$。

Code

---

如果您想练练类似的题目的话，推荐一下。

P2048 [NOI2010] 超级钢琴

代码确实简单，就不放了。