CF1832D2 Red-Blue Operations (Hard Version)

简单版和困难版的唯一区别在于 $ n $ 和 $ q $ 的最大值。 给定一个包含 $ n $ 个整数的数组。最初，所有元素都是红色的。 你可以对数组多次进行如下操作。在第 $ i $ 次操作时，你选择数组中的一个元素，然后： - 如果该元素是红色的，它会增加 $ i $ 并变为蓝色； - 如果该元素是蓝色的，它会减少 $ i $ 并变为红色。 操作编号从 $ 1 $ 开始，即第一次操作某个元素会加 $ 1 $，依此类推。 你需要回答 $ q $ 个如下形式的询问： - 给定一个整数 $ k $，如果你对数组恰好进行 $ k $ 次操作，数组中的最小值最大可能是多少？ 注意，操作不会在不同询问之间产生影响，所有询问都是基于初始数组 $ a $ 进行的。

第一行包含两个整数 $ n $ 和 $ q $（$ 1 \le n, q \le 2 \times 10^5 $），分别表示数组的元素个数和询问的数量。 第二行包含 $ n $ 个整数 $ a_1, a_2, \dots, a_n $（$ 1 \le a_i \le 10^9 $）。 第三行包含 $ q $ 个整数 $ k_1, k_2, \dots, k_q $（$ 1 \le k_j \le 10^9 $）。

对于每个询问，输出一个整数，表示经过恰好 $ k $ 次操作后，数组可能达到的最大最小值。

由 ChatGPT 4.1 翻译