#P18698. Maximum Bitwise OR
Maximum Bitwise OR
Maximum Bitwise OR
给定一个包含 个整数的数组 ,以及 个询问。
每个询问给出两个整数 。从原数组取出子数组,构成长度为 的新数组 ,其中 。
一次操作按顺序完成以下步骤:
- 选择下标 ,满足 ;
- 选择一个非负整数 ,满足 ;
- 将 替换为 ,其中 表示按位异或。
对于每个询问,求经过任意次操作后, 中所有元素的按位或能够达到的最大值,以及达到这个最大值所需的最少操作次数。
每个询问都重新从原数组构造 ,各询问之间互不影响。
输入格式
第一行包含整数 ,表示测试用例数。
对于每个测试用例:
- 第一行包含两个整数 ;
- 第二行包含 个整数 ;
- 接下来 行,每行包含两个整数 ,表示一个询问。
数据范围
- ;
- ;
- ;
- ;
- ;
- 所有测试用例的 之和不超过 ;
- 所有测试用例的 之和不超过 。
输出格式
对于每个测试用例,按询问顺序输出 行。每行输出两个以空格分隔的整数:该询问的最大按位或值,以及达到它所需的最少操作次数。
样例输入
1
3 2
10 10 5
1 2
1 3
样例输出
15 2
15 0
样例说明
对于第一个询问,初始 。可以执行两次操作:
- 选择 ,得到 ;
- 选择 ,得到 。
此时按位或为 ,这是能够达到的最大值,且至少需要两次操作。
对于第二个询问,初始 的按位或已经为 ,且可以证明不能更大,因此不需要操作。