XOR and Inversion 题解

· · 题解

我操，单 \log 彻底怒了。单 \log 指出了最核心的矛盾点：如果 std 写的常数足够小，怎么可能 \log^2 轻轻松松直接通过？这确实是我的严重错误。我需要彻底承认 std 写的不够好，想办法把 DLESS Round 糊弄过去。

以下设 h 表示题面中的 n，n=2^h。

首先考虑一个性质：操作是有结合律的。

例如，先执行 p_i:=p_i\oplus x_1，再执行 p_i:= p_i\oplus x_2，相当于执行一次 p_i=p_i\oplus x_1\oplus x_2，操作二也是类似。

于是现在相当于我们对排列 p，每次给出 x_1,x_2，求排列 p' 使得 p'_i=p_{i\oplus x_2}\oplus x_1 的逆序对数。

不妨先考虑一下没有操作一怎么做。

考虑我们平时有什么方式求逆序对，考虑通过分治的方式求逆序对。

考虑当 n 为 2 的幂次时，每次分治时，我们都会将一个区间 [k2^p,(k+1)2^p) 分成两个区间 [2k2^{p-1},(2k+1)2^{p-1}),[(2k+1)2^{p-1},(2k+2)2^{p-1})，然后再归并求出跨过中点的信息。

我们把分治过程中 p 相同的区间看作“一层”。

考虑如果 x_2 的第 p-1 位为 1 会发生什么，此时左右两个区间会交换，在计算跨过中点的信息时，逆序对数应当是原来的正序对数，可以发现，这种交换在每一层是独立的，即只有 x_2 的第 p 位为 1 时会交换第 p 层向上合并的贡献，对其它位没有影响。

于是，对于一层 p，我求出这一层向上合并时，跨过上一层中点的正序对数和逆序对数，即可轻松解决询问，时间复杂度 O((n+q)\log n)。

接下来考虑没有操作二怎么做。

发现一个排列的逆序对数等于其逆排列的逆序对数，所以仿照没有操作一的做法即可完成。

接下来，我们考虑两者都有的情况。

我们考虑先按下标分治，接下来在每次分治时，我们将中点左侧的标记为 0，右侧的标记为 1，然后再按值域分治，求出每一层中跨过中点的标记正序对数和逆序对数即可得到一个 O(n\log^2n+q\log^2n) 的做法。

实现时用线段树或 01-Trie 实现较为简便，实际上，这两种数据结构正是动态的分治。

代码。

先来考虑如何优化查询部分。

现在我们相当于有两张 \log n\times\log n 的表格，分别表示 x_1 与 x_2 的每一位两两之间的正序对和逆序对个数。

但是我们可以做更多的预处理，比如说我们把它变成两个 n\times\log n 的表格，表示 x_1 到 x_2 的每一位间的正逆序对个数，于是我们便可以支持单 \log 查询。

不过，我们可以把 n 分成高 \frac{h}{2} 位和低 \frac{h}{2} 位，分成 4 个 \sqrt{n}\times\sqrt{n} 的块，这样便可以支持单次 O(1) 查询，那么查询的复杂度已经达到了最优。

不过在本题的数据范围下单次查询 O(\log n) 也足以通过。

对于贡献的预处理部分，我们有至少两种 O(n\log n) 做法：

虚树做法

建一棵原排列的 01-Trie S，一棵逆排列的 01-Trie T，每次对于 S 上的一个节点求出该节点包含的数在 T 上的虚树，在虚树上 dp 求出贡献。

这种做法空间复杂度可以做到 O(n)，时间复杂度 O(n\log n)，不难证明，这两者都已经到达了最优复杂度。

可惜的是，这种做法常数要了命的大，即使在 n,q 在 10^6 级别的范围下仍然无法快于双 \log 做法，完全无法通过此题。

代码。

Trie 树合并做法

考虑分治，每次将分治左右两侧的 01-Trie 合并，并在合并过程中计算信息，当一个节点左右有来自不同 Trie 的子节点时，将它们子树中元素个数相乘更新贡献。

这种做法空间复杂度为 O(n\log n)，时间复杂度 O(n\log n)，不过常数并不是很大，可以获得 88 分。

代码。

（这一部分做法感谢帮我们审核的管理 ppip）

但是，真的只能获得 88 分吗？

常写树状数据结构的人肯定知道，我们可以进行垃圾回收。即，将删除的点重新在下次创建节点的时候利用。

在本题中，只要加了垃圾回收，Trie 树合并做法空间就是 O(n) 的。

此时，空间复杂度为同一时刻最多存在的节点数。

设一棵 Trie 中存了 k 个元素（并非节点），考虑把每一棵 Trie 分成上下两部分，上 \log k 层为上部分，剩下的为下部分。容易证明上下部分均只有 O(n) 个节点，所以总结点数为 O(n)。

于是，我们得到了常数并没有那么大的空间 O(n)，时间 O(n\log n+q) 做法。

代码。