#P18698. Maximum Bitwise OR

    ID: 18034 传统题 2000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-一维前缀和普通线段树暴力枚举提取最高置位

Maximum Bitwise OR

Maximum Bitwise OR

给定一个包含 NN 个整数的数组 A1,A2,…,ANA_1,A_2,\ldots,A_N,以及 QQ 个询问。

每个询问给出两个整数 L,RL,R。从原数组取出子数组,构成长度为 R−L+1R-L+1 的新数组 BB,其中 Bj=AL+j−1B_j=A_{L+j-1}。

一次操作按顺序完成以下步骤:

  1. 选择下标 jj,满足 1≤j≤R−L+11\le j\le R-L+1;
  2. 选择一个非负整数 ii,满足 2i≤Bj2^i\le B_j;
  3. 将 BjB_j 替换为 Bj⊕(Bj−2i)B_j\oplus(B_j-2^i),其中 ⊕\oplus 表示按位异或。

对于每个询问,求经过任意次操作后,BB 中所有元素的按位或能够达到的最大值,以及达到这个最大值所需的最少操作次数。

每个询问都重新从原数组构造 BB,各询问之间互不影响。

输入格式

第一行包含整数 TT,表示测试用例数。

对于每个测试用例:

  • 第一行包含两个整数 N,QN,Q;
  • 第二行包含 NN 个整数 A1,A2,…,ANA_1,A_2,\ldots,A_N;
  • 接下来 QQ 行,每行包含两个整数 L,RL,R,表示一个询问。

数据范围

  • 1≤T≤1051\le T\le 10^5;
  • 1≤N≤1051\le N\le 10^5;
  • 1≤Q≤1051\le Q\le 10^5;
  • 0≤Ai≤1090\le A_i\le 10^9;
  • 1≤L≤R≤N1\le L\le R\le N;
  • 所有测试用例的 NN 之和不超过 10510^5;
  • 所有测试用例的 QQ 之和不超过 10510^5。

输出格式

对于每个测试用例,按询问顺序输出 QQ 行。每行输出两个以空格分隔的整数:该询问的最大按位或值,以及达到它所需的最少操作次数。

样例输入

1
3 2
10 10 5
1 2
1 3

样例输出

15 2
15 0

样例说明

对于第一个询问,初始 B=[10,10]B=[10,10]。可以执行两次操作:

  1. 选择 j=1,i=0j=1,i=0,得到 B=[3,10]B=[3,10];
  2. 选择 j=2,i=2j=2,i=2,得到 B=[3,12]B=[3,12]。

此时按位或为 1515,这是能够达到的最大值,且至少需要两次操作。

对于第二个询问,初始 B=[10,10,5]B=[10,10,5] 的按位或已经为 1515,且可以证明不能更大,因此不需要操作。