CF1903D2 Maximum And Queries (hard version)

这是该问题的难度较高版本。两种版本的唯一区别在于 $n$ 和 $q$ 的约束条件、内存和时间限制。只有在所有版本都被解决后，你才能进行 Hack。 Theofanis 非常喜欢玩数字的二进制位。他有一个长度为 $n$ 的数组 $a$ 和一个整数 $k$。他最多可以对数组进行 $k$ 次操作。每次操作，他可以选择一个元素并将其加 $1$。 他想知道，在最多进行 $k$ 次操作后，数组 $a$ 能获得的最大按位与（bitwise AND）是多少。 Theofanis 为了找到这个值付出了很多努力，并且对自己的结果非常满意。不幸的是，Adaś 是个恶人，他反复更改 $k$ 的值来捉弄 Theofanis。 请帮助 Theofanis，对于 $q$ 个不同的 $k$，分别计算数组 $a$ 在最多进行 $k$ 次操作后可能获得的最大按位与。注意，每个询问都是独立的。

第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 10^6$），分别表示数组的长度和询问的数量。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i \le 10^6$），表示数组的元素。 接下来的 $q$ 行，每行包含一个整数 $k_i$（$0 \le k_i \le 10^{18}$），表示第 $i$ 次询问允许的操作次数。

对于每个询问，输出一个整数，表示在最多进行 $k_i$ 次操作后，数组 $a$ 能获得的最大按位与。

在第一个测试用例的第一个询问中，我们将第一个和最后一个元素各加 $1$。 此时数组变为 $[2,3,7,6]$，其按位与为 $2$。 在第二个测试用例的第一个询问中，我们将第一个元素加 $1$，第二个元素加 $5$，第三个元素加 $3$，此时所有元素都变为 $5$。 由 ChatGPT 4.1 翻译