← 返回题目列表

Codeforces · 2161/G

G. 按位与等于

中文机器翻译题面 查看原题

有一个整数数组 $$$a_1, a_2, \ldots, a_n$$$,并且有一个整数 $$$X$$$。

您可以执行以下操作零次或多次:

  • 选择$$$i$$$,并将$$$a_i$$$ 加一。

设 $$$a'$$$ 为数组的最终状态。您的目标是执行最少次数以上的操作,使得 $$$a'_1 \,\&\, a'_2 \,\&\, \ldots \,\&\, a'_n = X$$$。 $$$\&$$$ 表示按位与运算。

有 $$$q$$$ 这样的查询整数 $$$X$$$: $$$X_1, X_2, \ldots, X_q$$$。计算每个 $$$X = X_i$$$ 的答案。请注意,所有查询都是从相同的初始状态 $$$a$$$ 单独且独立地处理的。

输入

第一行包含整数 $$$n$$$ 和 $$$q$$$ ($$$2 \le n \le 200\,000$$$, $$$1 \le q \le 200\,000$$$) - 数组的长度和查询的数量。

第二行包含整数 $$$a_1, a_2, \ldots, a_n$$$ (对于每个 $$$i$$$, $$$0 \le a_i \lt 2^{20}$$$)。

接下来的 $$$q$$$ 行每行包含一个整数 $$$X_i$$$ ($$$0 \le X_i \lt 2^{20}$$$)。

输出

对于 $$$q$$$ 中的每个查询 $$$i$$$,打印到达数组 $$$a'$$$ 的最小操作数,使得 $$$a'_1 \,\&\, a'_2 \,\&\, \ldots \,\&\, a'_n = X_i$$$。

可以证明,在有限次数的操作中总是可以获得这样的数组$$$a'$$$。

示例

输入
复制

5 4
6 4 7 5 4
0
2
4
6

输出
复制

1
8
0
5

注意

对于第一个查询,可以增加 $$$i = 3$$$ ($$$a_i = 7$$$) 并得到数组 $$$a = [6, 4, 8, 5, 4]$$$,然后 $$$6 \,\&\, 4 \,\&\, 8 \,\&\, 5 \,\&\, 4 = 0$$$。

对于第三个查询,原始数组已匹配条件:$$$6 \,\&\, 4 \,\&\, 7 \,\&\, 5 \,\&\, 4 = 4$$$。