CF1540C2 Converging Array (Hard Version)

这是该问题的困难版本。唯一的区别在于本版本中 $1 \le q \le 10^5$。只有当你同时解决了两个版本的问题时，才能进行 hack。 有一个过程作用于长度为 $n$ 的数组 $a$ 和长度为 $n-1$ 的数组 $b$。 该过程是一个无限序列的操作。每次操作如下： - 首先，随机选择一个整数 $i$（$1 \le i \le n-1$）。 - 然后，同时将 $a_i$ 赋值为 $\min\left(a_i, \frac{a_i+a_{i+1}-b_i}{2}\right)$，并将 $a_{i+1}$ 赋值为 $\max\left(a_{i+1}, \frac{a_i+a_{i+1}+b_i}{2}\right)$，不进行任何取整（因此值可能变为非整数）。 具体操作示例见题目说明。可以证明，数组 $a$ 会收敛，即对于每个 $i$，存在极限值 $a_i$ 收敛到。定义函数 $F(a, b)$ 表示经过该过程后 $a_1$ 收敛到的值。 你给定了数组 $b$，但没有给定数组 $a$。不过，你还给定了第三个数组 $c$。如果数组 $a$ 满足所有元素均为整数，且 $0 \leq a_i \leq c_i$（$1 \leq i \leq n$），则称 $a$ 是“好”的。 你的任务是，对于 $q$ 个不同的 $x$，统计有多少个“好”的数组 $a$ 满足 $F(a, b) \geq x$。由于答案可能非常大，请对 $10^9+7$ 取模输出。

第一行包含一个整数 $n$（$2 \le n \le 100$）。 第二行包含 $n$ 个整数 $c_1, c_2, \ldots, c_n$（$0 \le c_i \le 100$）。 第三行包含 $n-1$ 个整数 $b_1, b_2, \ldots, b_{n-1}$（$0 \le b_i \le 100$）。 第四行包含一个整数 $q$（$1 \le q \le 10^5$）。 第五行包含 $q$ 个用空格分隔的整数 $x_1, x_2, \ldots, x_q$（$-10^5 \le x_i \le 10^5$）。

输出 $q$ 个整数，第 $i$ 个整数表示对于第 $i$ 个查询，有多少个“好”的数组 $a$ 满足 $F(a, b) \geq x_i$，对 $10^9+7$ 取模。

以下说明假设 $b = [2, 1]$，$c = [2, 3, 4]$（如样例所示）。 以下数组 $a$ 不是“好”的： - $a = [3, 2, 3]$ 不是“好”的，因为 $a_1 > c_1$； - $a = [0, -1, 3]$ 不是“好”的，因为 $a_2 < 0$。 一个可能的“好”数组 $a$ 是 $[0, 2, 4]$。可以证明，对该数组进行任何操作都不会改变它，因此 $F(a, b) = a_1 = 0$。 另一个可能的“好”数组 $a$ 是 $[0, 1, 4]$。若进行一次 $i = 1$ 的操作，则 $a_1 = \min(\frac{0+1-2}{2}, 0)$，$a_2 = \max(\frac{0+1+2}{2}, 1)$。所以操作后 $a$ 变为 $[-\frac{1}{2}, \frac{3}{2}, 4]$。可以证明，对该数组进行任何操作都不会改变它，因此 $F(a, b) = -\frac{1}{2}$。 由 ChatGPT 4.1 翻译