CF2146D2 Max Sum OR (Hard Version)

这是该问题的 Hard 版本。不同之处在于本版本中，$0 \leq l \leq r < 2^{30}$。只有在你解决了所有版本的本题后，才可以进行 Hack。 给定两个整数 $l$ 和 $r$（$l \leq r$）。 设 $n = r - l + 1$。我们将创建两个长度为 $n$ 的数组 $a$ 和 $b$。一开始，$a$ 和 $b$ 均为 $[l, l+1, \ldots, r]$。你的任务是任意重新排列数组 $a$，使下面的值最大化： $$ \sum_{i=1}^n \left (a_i\,|\,b_i \right ) $$ 其中，$|$ 表示[按位或运算](https://en.wikipedia.org/wiki/Bitwise_operation#OR)。 你还需要给出一种重新排列数组 $a$ 的方案。

每组测试包含多组数据。第一行包含整数 $t$（$1 \leq t \leq 10^4$），表示测试组数。 接下来每组测试一行，包含两个整数 $l$ 和 $r$（$0 \leq l \leq r < 2^{30}$），即数组 $a$ 的最小和最大元素。 设 $n = r - l + 1$。保证所有测试用例中，所有 $n$ 之和不超过 $2 \cdot 10^5$。

对于每组测试数据，输出两行。 第一行输出一个整数，表示最大的 $\sum\limits_{i=1}^n (a_i\,|\,b_i)$。 第二行输出 $n$ 个两两不同的整数 $a_1, a_2, \ldots, a_n$，表示重新排列后的数组 $a$。 如果有多种方案，可以任选其一输出。

在第一个测试用例中，重排后的数组 $a$ 为 $[3,2,1,0]$。表达式值为 $(3\,|\,0)+(2\,|\,1)+(1\,|\,2)+(0\,|\,3)=3+3+3+3=12$。可以证明这是表达式最大可能值。 在第二个测试用例中，重排后的数组 $a$ 为 $[7,8,5,4,3,2,9,0,1,6]$。表达式值为 $90$。可以证明这是最大可能值。 在第三个测试用例中，可以证明 $240$ 是表达式最大可能值。 在第四个测试用例中，重排后的数组 $a$ 为 $[10,8,7,6,9]$。表达式值为 $(10\,|\,6)+(8\,|\,7)+(7\,|\,8)+(6\,|\,9)+(9\,|\,10)=14+15+15+15+11=70$。可以证明这是最大可能值。 由 ChatGPT 5 翻译