A16684. Bitwise And Equals
编程题
NOI/NOI+/CTSC
知识点
题目描述
给定一个整数数组 $a_1, a_2, \ldots, a_n$，还有一个整数 $X$。
你可以执行如下操作任意次（可以是零次）：
- 选择一个 $i$，并将 $a_i$ 增加 $1$。
设 $a'$ 是最终状态下的数组。你的目标是用最少的操作次数使得 $a'_1\,\&\,a'_2\,\&\,\ldots\,\&\,a'_n = X$。其中 $\&$ 表示按位与运算。
有 $q$ 个查询整数 $X$：$X_1, X_2, \ldots, X_q$。请你对于每个 $X = X_i$ 求出答案。注意所有查询都是在相同的初始数组 $a$ 下独立进行。
你可以执行如下操作任意次（可以是零次）：
- 选择一个 $i$，并将 $a_i$ 增加 $1$。
设 $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 < 2^{20}$）。
接下来 $q$ 行，每行一个整数 $X_i$（$0 \le X_i < 2^{20}$）。
第二行包含整数 $a_1, a_2, \ldots, a_n$（对于每个 $i$，$0 \le a_i < 2^{20}$）。
接下来 $q$ 行，每行一个整数 $X_i$（$0 \le X_i < 2^{20}$）。
输出格式
对于每个查询 $i$（共 $q$ 个），输出使数组 $a'$ 满足 $a'_1\,\&\,a'_2\,\&\,\ldots\,\&\,a'_n = X_i$ 所需的最小操作次数。
可以证明，总能在有限次数内得到满足条件的数组 $a'$。
可以证明，总能在有限次数内得到满足条件的数组 $a'$。
输入输出样例
输入 #1
5 4 6 4 7 5 4 0 2 4 6
输出 #1
1 8 0 5
说明/提示
对于第一个查询，你可以将第 $i = 3$ 个元素（$a_i = 7$）增加 $1$，得到数组 $a = [6, 4, 8, 5, 4]$，此时 $6\,\&\,4\,\&\,8\,\&\,5\,\&\,4=0$。
对于第三个查询，原数组已经满足条件：$6\,\&\,4\,\&\,7\,\&\,5\,\&\,4=4$。
对于第三个查询，原数组已经满足条件：$6\,\&\,4\,\&\,7\,\&\,5\,\&\,4=4$。