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$ 做法，完全无法通过此题。

代码。

考虑分治，每次将分治左右两侧的 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)$ 做法。

代码。