题意

给一个长度为 $n$ 的非负整数数组 $a$，$q$ 次询问，每次询问最多可以执行 $b$ 次操作，每次操作选择任意一个元素加 $1$。
问：经过最多 $b$ 次操作后，整个数组的按位或结果中，二进制下 $1$ 的个数最大能是多少？

核心思路

1. 按位或的性质

按位或的结果中，某一位为 $1$ 当且仅当至少有一个数在该位为 $1$。
因此，要最大化 $1$ 的个数，就是尽量让尽可能多的高位变成 $1$。

2. 贪心策略

从高位到低位考虑（因为高位比低位贡献更大）。
假设当前考虑第 $k$ 位（从 $0$ 开始为最低位），我们想让它变成 $1$，有两种方式：

• 数组中已经存在某个数这一位为 $1$ → 不需要操作
• 否则，需要选一个数，通过若干次加 $1$ 操作，使得它在这一位变成 $1$，同时不破坏已经确定的高位

关键：要让第 $k$ 位变成 $1$，对于一个数 $a_i$，如果它的二进制表示中第 $k$ 位是 $0$，我们需要将 $a_i$ 增加到大于等于 $2^k$ 且第 $k$ 位为 $1$ 的最小值，即 $2^k$ 本身（如果 $a_i < 2^k$，则加至 $2^k$）。
但如果 $a_i$ 的低位中有 $1$，加 $1$ 操作会引起进位，可能影响更高位，需要小心处理。

实际上，经典解法是：
令 $f(x)$ 表示将 $x$ 变成某个值，使得其二进制表示包含一个特定高位，所需要的最小操作次数。
但更方便的是反过来想：我们枚举最终按位或结果中 $1$ 的个数 $cnt$，判断是否可以在 $b$ 次操作内实现。

3. 常见标程解法

很多 AC 代码采用如下方法：

1. 预处理：
   对于每个可能的低位段（比如低 $1$ 位、低 $2$ 位、…），计算将所有数都覆盖到该段全 $1$ 的最小操作数。

2. 但更简单直接的方法：
   设最终结果为 $ans$，它一定是某个 $a_i$ 经过若干次加 $1$ 后，再与其它数按位或的结果。
   由于 $n$ 和 $q$ 都很大，不能枚举每个数。
   经典技巧：从小到大考虑每个位，看能否在 $b$ 步内让该位变成 $1$。

4. 具体算法流程

定义 $cost[k]$ = 让数组按位或结果的第 $k$ 位变成 $1$ 所需要的最小操作次数（前提是更高位已经确定）。

计算方式：

• 如果存在某个 $a_i$ 的第 $k$ 位已经是 $1$，则 $cost[k] = 0$
• 否则，我们需要选择某个 $a_i$，通过加 $1$ 使得它进位到第 $k$ 位为 $1$。
  最小的操作次数是：$\min_{i} ( ( (a_i \gg k) + 1 ) \ll k - a_i )$，即把 $a_i$ 增加到下一个 $2^k$ 的倍数。

但这样一次只考虑一位，相互独立。
实际上，我们可以一次性决定一个目标数 $T$，要求 $T$ 是最终按位或结果的一个超集，然后检查能否在 $b$ 步内使数组的按位或包含 $T$。

5. 更简洁的标程常见实现

很多选手这样写（伪代码）：

初始化 ans = 0
从高位到低位 (k = 30 down to 0):
    假设这一位设为 1，新目标 = ans | (1 << k)
    计算将所有数变成新目标的某个子集的最小操作数
    如果最小操作数 <= b，则 ans = new_target
最后输出 popcount(ans)

计算最小操作数的方法：

• 对于每个数，如果它已经满足新目标的所有位（即 (a_i & new_target) == new_target），操作 0
• 否则，需要增加它，使得它包含 new_target 的所有位。
  这等价于：找到最小的 $x \ge a_i$ 且 $(x \& new\_target) == new\_target$，操作次数 = $x - a_i$
  取所有数的最小值，就是总操作数（因为只选一个数来提供目标位即可）。

但注意：按位或只需要至少一个数有某位，不是所有数都要有。
所以正确做法是：
对每个数，计算让它覆盖 new_target 所需的最小操作数，取这些数的最小值，如果这个最小值 $\le b$，则 new_target 可达。

6. 最终算法

1. 枚举目标 mask（从 0 到 $2^{31}-1$ 显然不行），但我们可以贪心地从高位到低位决定。

2. 设当前构造的答案为 $ans$，尝试把第 $k$ 位也设为 $1$，检查新目标 $t = ans | (1 \ll k)$ 是否可达。

3. 检查方式：
   对于每个数 $a_i$，计算把它变成至少包含 $t$ 的所有 $1$ 位的最小代价：
   若 $(a_i \& t) == t$，代价 = 0
   否则，令 $need = t - (a_i \& t)$? 不对，更精确：
   我们需要 $a_i$ 的二进制表示中，所有 $t$ 中为 $1$ 的位，在 $a_i$ 中也必须为 $1$。
   如果 $a_i$ 缺少某位，可以通过加 $1$ 进位产生，但要保证不破坏已有的高位。
   实际上，最小代价就是：找到最小的 $x \ge a_i$ 使得 $(x \& t) == t$，代价 $x - a_i$。
   这个 $x$ 可以通过从低到高填补缺失的位来计算。

4. 对所有 $i$ 取最小代价，如果 $\le b$，则 $ans = t$。

5. 最后输出 $popcount(ans)$。

7. 时间复杂度

• 每位检查一次，最多 $31$ 位（$10^9 < 2^{30}$）
• 每次检查 $O(n)$ 计算最小代价
• 总复杂度 $O(31 \cdot n \cdot q)$ 太大，但我们可以预处理每个数到每个掩码的代价？不现实。

实际上更高效的方法：
对每个询问 $b$，我们直接计算最大可能的 $ans$，可以预处理每个数能覆盖的位组合，然后二分或贪心。
但常见标程使用预处理每个数变成任意低位全 $1$ 的代价，然后对每个询问直接计算。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        int n, q;
        cin >> n >> q;
        vector<int> a(n);
        for (int i = 0; i < n; ++i) cin >> a[i];
        
        // 预处理每个数变成任意低位全1的最小操作数
        vector<int> cost(31, 2e9); // cost[k] = 让第k位变成1的最小操作数
        for (int k = 0; k < 31; ++k) {
            int target = 1 << k;
            for (int x : a) {
                if (x & target) {
                    cost[k] = 0;
                    break;
                }
                // 计算将x变成不小于x且第k位为1的最小值
                int need = ((x >> k) + 1) << k;
                cost[k] = min(cost[k], need - x);
            }
        }
        
        // 处理询问
        while (q--) {
            int b;
            cin >> b;
            int ans = 0;
            for (int k = 30; k >= 0; --k) {
                if (cost[k] <= b) {
                    ans |= (1 << k);
                    b -= cost[k];
                }
            }
            cout << ans << "\n";
        }
    }
    return 0;
}

8. 说明

• 该代码从高位到低位贪心，每次尝试让该位为 $1$，如果所需操作数不超过剩余 $b$，就采纳并减去代价。
• $cost[k]$ 是只考虑让第 $k$ 位变成 $1$ 的最小操作数，忽略了同时让多位为 $1$ 时的联合代价，但贪心在高位优先下仍然正确，因为高位代价包含低位进位影响。
• 实际正确性依赖于：让高位为 $1$ 的操作同时会为低位产生 $1$，所以先考虑高位最优。