A16632 | $Max Sum OR (Hard Version)$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

这是该问题的 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$。 如果有多种方案，可以任选其一输出。

输入输出样例

输入 #1

7
0 3
0 9
0 15
6 10
1 4
3 6
1000000007 1000000009

输出 #1

12
3 2 1 0 
90
7 8 5 4 3 2 9 0 1 6
240
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 
70
10 8 7 6 9
20
2 1 4 3 
28
4 3 6 5 
3000000039
1000000008 1000000007 1000000009

C++ 编辑器

输入

输出

A16632 | Max Sum OR (Hard Version)

题目描述

输入格式

输出格式

输入输出样例

A16632 | $Max Sum OR (Hard Version)$