CF2147E.Maximum OR Popcount

You are given an array of $n$ non-negative integers.

You want to answer given $q$ independent scenarios. In the $i$-th scenario, you are allowed to perform the following operation at most $b_i$ times:

• Choose an element of the array and increase it by $1$.

Your goal is to maximize the number of bits that are equal to $1$ in the bitwise OR of all numbers in the array. Find this number for each scenario.

给你一个包含 $n$ 个非负整数的数组。

你需要回答 $q$ 个相互独立的询问。在第 $i$ 个询问中，你最多可以执行以下操作 $b_i$ 次：

• 选择数组中的一个元素，并将其加 $1$。

你的目标是最大化该数组中所有数字的按位或结果中值为 $1$ 的比特位数量。对每个询问，求出该最大值。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^3$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $q$ ($1 \leq n, q \leq 10^{5}$) — the size of the array and the number of scenarios.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 10^{9}$) — the elements of the array.

The $i$-th of the next $q$ lines contains a single integer $b_i$ ($0 \leq b_i \leq 10^{9}$) — the maximum number of operations allowed in the $i$-th scenario.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^{5}$, and the sum of $q$ over all test cases does not exceed $10^{5}$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^3$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $q$（$1 \leq n, q \leq 10^{5}$）—— 分别表示数组的大小和场景数量。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \leq a_i \leq 10^{9}$）—— 表示数组的元素。

接下来的 $q$ 行中，第 $i$ 行包含一个整数 $b_i$（$0 \leq b_i \leq 10^{9}$）—— 表示第 $i$ 个场景中允许的最大操作次数。

保证所有测试用例的 $n$ 之和不超过 $10^{5}$，且所有测试用例的 $q$ 之和不超过 $10^{5}$。

For each test case, output $q$ lines, the $i$-th of them containing a single integer — the maximum possible number of bits equal to $1$ in the bitwise OR in the $i$-th scenario.

对于每个测试用例，输出 $q$ 行，其中第 $i$ 行包含一个整数——即第 $i$ 个场景下按位或（bitwise OR）结果中等于 $1$ 的比特位的最大可能数量。

Visualizer link

In the first test case:

• In the first scenario, we don't have any operations, and therefore the answer is equal to the number of $1$-bits in the bitwise OR of the original array, $0$, which has $0$ bits set in its binary representation.
• In the second scenario, one way of achieving $1$ bit set in the bitwise OR is increasing $a_1$ by $1$ twice, obtaining a bitwise OR of $2={(10)}_2$. It can be shown that it is the best possible value we can obtain by performing the operation at most twice.
• In the third scenario, one way of achieving a result of $2$ is adding $1$ to $a_1$ three times, which can be shown to be optimal. Note that you don't have to apply the operation $4$ times.

In the second test case:

• In the first scenario, we don't have any operations, and therefore the answer is equal to the number of $1$-bits in the bitwise OR of the original array, which is $2$.
• In the second scenario, one way of achieving a result of $3$ is adding $1$ to $a_2$ three times, which can be shown to be optimal.

可视化链接

在第一个测试用例中：

• 在第一种情形下，不执行任何操作，因此答案等于原数组按位或结果（即 $0$）的二进制表示中 $1$ 的个数，为 $0$。
• 在第二种情形下，一种使按位或结果中 $1$ 的个数达到 $1$ 的方法是将 $a_1$ 增加 $1$ 两次，得到按位或结果为 $2={(10)}_2$。可以证明，在最多执行两次操作的前提下，这是所能达到的最优值。
• 在第三种情形下，一种使结果达到 $2$ 的方法是将 $a_1$ 增加 $1$ 三次，可以证明该方案是最优的。注意：你无需恰好执行 $4$ 次操作。

在第二个测试用例中：

• 在第一种情形下，不执行任何操作，因此答案等于原数组按位或结果的二进制表示中 $1$ 的个数，为 $2$。
• 在第二种情形下，一种使结果达到 $3$ 的方法是将 $a_2$ 增加 $1$ 三次，可以证明该方案是最优的。