异或交换与字典序最小化

思路推导

两个非负整数的异或值小于 $4$，等价于它们从第 $2$ 位起的全部二进制位都相同，也就是除以 $4$ 向下取整的结果相同。

将数 $x$ 归入编号 $\lfloor x/4\rfloor$ 的组。一次合法交换只会移动同一组内的元素，所以每个位置所属的组不会改变。反过来，同组内任意两个元素都可以直接交换，因此该组中的值能够按任意顺序放到该组占据的位置上。

做法

遍历数组，将每个值加入其所属组的序列。对每组的值升序排序，并为每组维护当前已取走的元素个数。再次从左到右遍历原数组，每次从该位置对应组取出尚未使用的最小值。

正确性证明

每次输出的值都来自该位置所属组，而且每个值恰好使用一次。由于每组内部可任意置换，整个输出数组可以由合法交换得到。

考虑任何其他合法结果与本算法结果第一个不同的位置。两个结果此前已使用相同的前缀，因此在这个位置对应组中，尚可使用的元素多重集相同。本算法取出其中最小的值，所以该位置不可能比其他合法结果更大。如果两者在此不同，本算法的值必然更小。因此本算法得到唯一的字典序最小数组。

复杂度

有序映射收集和访问各组共花费 $O(n\log n)$ 时间。所有组排序的总时间不超过 $O(n\log n)$。单个测试用例的总时间复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$。多组测试的总规模遵守题面聚合限制。

部分分思路

极小规模可以直接将数组看作状态，枚举每次合法交换到达的新状态，在有限状态图中搜索并取字典序最小者。状态数不超过 $n!$，每个状态检查 $O(n^2)$ 次交换。

中等规模可以枚举原位置间所有合法交换边，使用并查集找到连通分量，然后在每个分量的位置中依次放入排序后的元素。边枚举花费 $O(n^2\alpha(n))$ 时间，分量内排序花费 $O(n\log n)$ 时间。

当值域很小时，可以使用覆盖整个值域的频次数组。遍历原位置时，只需检查与原值高位相同的四个候选值并消耗最小的剩余值。若当前测试用例的最大元素为 $U$，时间为 $O(n+U)$，空间为 $O(n+U)$。扩大到原题值域后，直接开值域数组不再满足内存限制，需要使用稀疏分组。