D1. 极大和或(简单版)
每次测试时间限制:2 秒
每次测试内存限制:256 兆字节
这是问题的简单版本。两个版本的区别在于,在这个版本中,l=0,且 r<2×105。只有你解决了这个问题的所有版本,才能破解。
题目描述
你被赋予两个整数 l 和 r(l≤r)。
设 n=r−l+1。我们将创建两个数组 a 和 b,两者均由 n 个整数组成。
最初,a 和 b 都等于 [l,l+1,…,r]。
你必须重新排序数组 a,以最大化以下值:
i=1∑n(ai ∣ bi)
这里,∣ 表示按位的 OR 运算。
你还需要构造一种可能的重新排序数组 a 的方法。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 t(1≤t≤104)。
以下是测试用例的描述。
每个测试用例中唯一的行包含两个整数 l 和 r(0=l≤r<2×105)—— 分别是 a 中的最小和最大元素。
设 n=r−l+1。保证所有测试用例的 n 之和不超过 2×105。
输出
对于每个测试用例:
- 在第一行打印一个整数 —— 即最大值 ∑i=1n(ai ∣ bi)。
- 在第二行打印 n 个不同的整数 a1,a2,…,an —— 重新排序后的数组 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。可以证明这是表达式的最大可能值。