哈喵~！冒险者大人，欢迎来到我的小解说屋，喵~。今天我们要一起探险的题目是 G. XOUR，看起来有点吓人，但别担心，跟着我的猫爪印，我们一定能找到宝藏的，的说！

题目大意喵~

是这样的，我们拿到一个装着 n 个非负整数的数组 a。我们有一种特殊的魔法，可以交换数组里 i 位置和 j 位置的两个数字 a_i 和 a_j，但前提是 a_i XOR a_j < 4。这里的 XOR 就是按位异或操作啦。

我们可以尽情地使用这个魔法，次数不限。我们的目标是，通过这些交换，让整个数组的字典序变得最小。

字典序最小是什么意思呢？就是像查字典一样，我们希望数组开头的数字尽可能小。如果第一个数字一样，就比第二个，以此类推。比如数组 [0, 1, 2, 3] 就比 [1, 0, 3, 2] 的字典序要小，因为它在第一个位置就更小啦，喵~。

解题思路的说

这个问题最关键的地方，就是那个神秘的交换条件 a_i XOR a_j < 4。我们得像小猫一样，用好奇心去拨开它神秘的面纱，喵！

1. 勘破交换条件的秘密

a_i XOR a_j < 4 意味着 a_i XOR a_j 的结果只能是 0, 1, 2, 或 3。我们把这些数字写成二进制看看：

• 0 -> 00
• 1 -> 01
• 2 -> 10
• 3 -> 11

发现了喵？这些数字的特点是，从第 2 位（也就是值为 4 的那一位）开始，所有更高的位都是 0！

两个数进行异或操作时，如果某一位相同，结果就是 0；如果不同，结果就是 1。要想让异或结果的高位（第 2 位及以上）全部是 0，就意味着 a_i 和 a_j 在这些高位上必须是完全一样的！它们只允许在最低的两位（第 0 位和第 1 位）上有所不同。

怎么判断两个数除了最低两位之外都相同呢？我们可以用一个位掩码 ~3。在二进制里，3 是 ...0011，~3（按位取反）就是 ...1100。任何数和 ...1100 进行按位与（&）操作，就会把最低两位清零，而保留所有高位。

所以，我们的交换条件 a_i XOR a_j < 4 就等价于 (a_i & ~3) == (a_j & ~3)！

2. 发现可以分组喵！

这个新条件 (a_i & ~3) == (a_j & ~3) 告诉我们，所有 & ~3 结果相同的数，它们之间是可以互相交换的（可能是通过别的数作为跳板间接交换）。这就像是把数字们分进了不同的小团体！

• 团体内部：同一个团体里的任何两个成员，都可以通过一系列交换，到达团体内的任何一个位置。所以我们可以把团体内的所有数值，任意地排列在这些位置上。
• 团体之间：不同团体的成员，它们的 & ~3 值不同，所以它们永远无法跨越团体的界限进行交换。

这在数学上叫做一个“等价关系”，它把我们的数组划分成了若干个互不相交的“等价类”（也就是我们说的小团体）。

3. 如何得到字典序最小呢？

我们的目标是让最终的数组 b 字典序最小。这意味着我们要让 b[0] 尽可能小，然后是 b[1]，以此类推。

考虑一下，对于每个小团体，它所拥有的 值的集合 和 位置的集合 都是固定的。 比如说，在 a = [2, 7, 1, 5, 6] 这个例子中：

• 2 & ~3 = 0
• 7 & ~3 = 4
• 1 & ~3 = 0
• 5 & ~3 = 4
• 6 & ~3 = 4

我们有两个团体：

• 团体A (key=0): 拥有数值 {1, 2}，它们最初在位置 {0, 2}。
• 团体B (key=4): 拥有数值 {5, 6, 7}，它们最初在位置 {1, 3, 4}。

为了让最终数组字典序最小，我们必须在每个团体内部做出最优选择。对于团体A，它占据了位置 {0, 2}。为了让 b[0] 尽可能小，我们应该把团体A里最小的值 1 放在 0 号位，另一个值 2 放在 2 号位。 同样，对于团体B，它占据了位置 {1, 3, 4}。我们应该把团体B里最小的三个值 {5, 6, 7} 按顺序放在这三个位置上，也就是 b[1]=5, b[3]=6, b[4]=7。

所以，最终的策略就是：

1. 识别团体：根据 val & ~3 的值（我们称之为 key）给所有元素分组。
2. 内部排序：对于每个团体，我们把它的所有 数值 从小到大排序，也把它的所有 位置（下标） 从小到大排序。
3. 重新填充：将排序后的数值，依次填入排序后的位置中。

4. 实现方法

代码里的实现非常巧妙，喵~！它没有显式地去建立每个组，而是通过两次排序完成了这个过程：

1. 创建一个 (key, value) 对的列表 keyed_values。
2. 创建一个 (key, index) 对的列表 keyed_indices。
3. 对 keyed_values 排序。排序时会先按 key 排，key 相同再按 value 排。这样，所有值就在各自的组内排好序了。
4. 对 keyed_indices 排序。同样，先按 key 排，key 相同再按 index 排。这样，所有位置就在各自的组内排好序了。
5. 现在，keyed_values[i] 和 keyed_indices[i] 属于同一个组，并且分别是该组排序后的第 k 个值和第 k 个位置。我们只需要把这个值 keyed_values[i].second 放到那个位置 keyed_indices[i].second 就行啦！

参考代码的说

这是冒险者大人提供的代码，我已经加上了我的猫爪注释，希望能帮助你理解，喵~

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

void solve() {
    int n;
    std::cin >> n;
    // 存放 (分组key, 数值)
    std::vector<std::pair<int, int>> keyed_values(n);
    // 存放 (分组key, 原始下标)
    std::vector<std::pair<int, int>> keyed_indices(n);

    for (int i = 0; i < n; ++i) {
        int val;
        std::cin >> val;
        // 条件 a_i XOR a_j < 4 等价于 a_i 和 a_j 除了最低两位外都相同。
        // 我们可以用 val & ~3 来计算这个 "分组key"。
        int key = val & ~3;
        keyed_values[i] = {key, val};
        keyed_indices[i] = {key, i};
    }

    // 1. 对值进行排序。首先按分组key排序，key相同则按值本身大小排序。
    //    这相当于把每个组内的值排好了序。
    std::sort(keyed_values.begin(), keyed_values.end());
    
    // 2. 对原始下标进行排序。首先按分组key排序，key相同则按下标大小排序。
    //    这相当于把每个组占据的位置排好了序。
    std::sort(keyed_indices.begin(), keyed_indices.end());

    std::vector<int> b(n);
    // 3. 为了让最终数组字典序最小，我们必须把一个组内排好序的值，
    //    放入该组排好序的位置中。
    //    这个循环通过匹配排序后的 keyed_values 和 keyed_indices 的第 i 个元素来实现这一点。
    for (int i = 0; i < n; ++i) {
        // keyed_indices[i].second 是排序后第 i 个位置
        // keyed_values[i].second 是排序后第 i 个值
        // 把正确的值放到正确的位置上
        b[keyed_indices[i].second] = keyed_values[i].second;
    }

    for (int i = 0; i < n; ++i) {
        std::cout << b[i] << (i == n - 1 ? "" : " ");
    }
    std::cout << "\n";
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

相关知识点小课堂

位运算 (Bitwise Operations)

• XOR (异或): 两个二进制位不同时结果为1，相同时为0。比如 5 (101) XOR 3 (011) = 6 (110)。
• & (按位与): 两个二进制位都为1时结果才为1，否则为0。比如 5 (101) & 3 (011) = 1 (001)。
• ~ (按位非): 将所有二进制位反转，0变1，1变0。
• val & ~3: 这是本题的关键技巧！3 的二进制是 ...0011。~3 就是 ...1100。val & ...1100 会保留 val 的所有高位（从第2位开始），同时把最低两位强制变成0。这就得到了我们分组用的 key。

字典序 (Lexicographical Order)

就像查英文字典一样，先比较第一个字母，第一个相同就比较第二个，以此类推。对于数组，就是先比较第一个元素，第一个元素相同就比较第二个，直到找到第一个不同的位置，那个位置上元素更小的数组，其字典序就更小。

等价关系与划分 (Equivalence Relation & Partition)

这是一个稍微理论一点的概念，喵~。一个关系（比如我们的“可以交换”）如果满足：

1. 自反性: a 可以和 a 交换。(a XOR a = 0 < 4，满足)
2. 对称性: 如果 a 可以和 b 交换，那么 b 也可以和 a 交换。(a XOR b = b XOR a，满足)
3. 传递性: 如果 a 和 b 能换，b 和 c 能换，那么 a 和 c 也能换。(我们之前分析过，a,b,c 的高位都相同，所以满足)

满足这三条的关系就是等价关系。一个等价关系会自然地把一个集合（这里是数组元素）分成若干个互不相干的子集（划分），每个子集就是一个等价类（我们口中的“团体”）。

好啦，这次的探险就到这里啦！希望我的解说对冒险者大人有帮助，喵~。如果还有不懂的，随时可以再来找我玩哦！