← 返回题目列表

Codeforces · 2146/D1

D1. 最大和或(简单版)

中文机器翻译题面 查看原题

这是问题的简单版本。版本之间的区别在于,在这个版本中,$$$l=0$$$ 和$$$r \lt 2\cdot 10^5$$$。只有解决了该问题的所有版本,您才能破解。

给定两个整数 $$$l$$$ 和 $$$r$$$ ($$$l\le r$$$)。

令 $$$n = r - l + 1$$$。我们将创建两个数组 $$$a$$$ 和 $$$b$$$,均由 $$$n$$$ 整数组成。最初,$$$a$$$ 和$$$b$$$ 都等于$$$[l, l+1, \ldots, r]$$$。您必须任意重新排序数组 $$$a$$$ 才能最大化以下值:

$$\sum_{i=1}^n \left (a_i\;|\;b_i \right ).$$

这里,$$$|$$$ 表示按位或运算。

您还需要构造一种可能的方法来重新排序数组$$$a$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的唯一行包含两个整数 $$$l$$$ 和 $$$r$$$ ($$$0=l\leq r \lt 2\cdot 10^5$$$) — $$$a$$$ 中的最小和最大元素。

设 $$$n = r - l + 1$$$。保证所有测试用例的$$$n$$$总和不超过$$$2\cdot 10^5$$$。

输出

对于每个测试用例,在输出的第一行打印一个整数 - $$$\sum\limits_{i=1}^n \left (a_i\;|\;b_i \right )$$$ 的最大值。

然后,在第二行打印 $$$n$$$ 不同的整数 $$$a_1, a_2, \ldots,a_n$$$ — 重新排序后的数组 $$$a$$$ 。

如果有多个答案,您可以打印其中任何一个。

示例

输入
复制

3
0 3
0 9
0 15

输出
复制

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

注意

在第一个测试用例中,重新排序的数组 $$$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$$$。可以证明这是表达式的最大可能值。