CF2147E Maximum OR Popcount

给定一个长度为 $n$ 的非负整数数组。 你需要回答 $q$ 个相互独立的场景。在第 $i$ 个场景中，你最多可以进行 $b_i$ 次如下操作： - 选择数组中的一个元素并将其加 $1$。 你的目标是最大化数组所有元素按位或的结果中 $1$ 的位数。对于每个场景，求出能够达到的最多 $1$ 的位数。

每组测试数据包含多组测试用例。第一行包含一个整数 $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$ 行，每行一个整数 $b_i$（$0 \leq b_i \leq 10^{9}$），表示第 $i$ 个场景最多可以操作的次数。 保证所有测试用例中 $n$ 的总和不超过 $10^5$，$q$ 的总和不超过 $10^5$。

对于每组测试，用 $q$ 行输出结果，第 $i$ 行输出第 $i$ 个场景下，所有元素按位或后 $1$ 的位数可以达到的最大值。

[可视化链接](https://codeforces.com/assets/contests/2147/E_HLZmcINLu6bzC9EaTZrI.html) 在第一个测试用例中： - 场景一中没有操作，因此答案等于初始数组按位或后的 $1$ 的个数，即 $0$，它的二进制表示中有 $0$ 个 $1$。 - 场景二中，例如对 $a_1$ 加 $1$ 两次，得到了按位或为 $2 = (10)_2$。可以证明这是最多能达到的 $1$ 位数。 - 场景三中，通过对 $a_1$ 加 $1$ 三次，可以得到按位或为 $3=(11)_2$，可以证明这是最优的结果。不需要进行 $4$ 次操作。 在第二个测试用例中： - 场景一没有任何操作，因此答案就是原始数组按位或后 $1$ 的个数，即 $2$。 - 场景二中，例如对 $a_2$ 加 $1$ 三次，可以得到按位或为 $3$ 个 $1$。这可以证明是最优结果。 由 ChatGPT 5 翻译