显然，对于正整数 $p,q$，设 $p,q$ 在二进制表示下的位数分别为 $x,y$，若 $p\le q$，则：

• $p \le p \oplus q$，当且仅当 $x \ne y$，因为若 $x=y$ 则 $p$ 和 $q$ 异或后最高位会抵消，$p \oplus q$ 一定小于 $p$ 和 $q$；
• $p \oplus q \le q$，当且仅当 $q$ 在二进制表示下的第 $x$ 位为 $1$，因为若 $q$ 在二进制表示下的第 $x$ 位为 $0$，则 $q$ 与 $p$ 异或后一定会变大。

要注意，对于任意非负整数 $m$，都满足 $0 \le 0 \oplus m \le m$，所以需要特判 $0$。

在特判 $0$ 后，我们可以把剩下的元素从小到大排序，开一个桶，把枚举过的数在二进制表示下的位数记录在桶里，动态地根据上面的讨论计算即可。

时间复杂度 $\mathcal O(n \log n+n \log V)$，其中 $V$ 为值域。

标题

思路

解题方法

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code