CF1540C2 Converging Array (Hard Version)

This is the hard version of the problem. The only difference is that in this version $ 1 \le q \le 10^5 $ . You can make hacks only if both versions of the problem are solved. There is a process that takes place on arrays $ a $ and $ b $ of length $ n $ and length $ n-1 $ respectively. The process is an infinite sequence of operations. Each operation is as follows: - First, choose a random integer $ i $ ( $ 1 \le i \le n-1 $ ). - Then, simultaneously set $ a_i = \min\left(a_i, \frac{a_i+a_{i+1}-b_i}{2}\right) $ and $ a_{i+1} = \max\left(a_{i+1}, \frac{a_i+a_{i+1}+b_i}{2}\right) $ without any rounding (so values may become non-integer). See notes for an example of an operation.It can be proven that array $ a $ converges, i. e. for each $ i $ there exists a limit $ a_i $ converges to. Let function $ F(a, b) $ return the value $ a_1 $ converges to after a process on $ a $ and $ b $ . You are given array $ b $ , but not array $ a $ . However, you are given a third array $ c $ . Array $ a $ is good if it contains only integers and satisfies $ 0 \leq a_i \leq c_i $ for $ 1 \leq i \leq n $ . Your task is to count the number of good arrays $ a $ where $ F(a, b) \geq x $ for $ q $ values of $ x $ . Since the number of arrays can be very large, print it modulo $ 10^9+7 $ .

N/A

N/A

The following explanation assumes $ b = [2, 1] $ and $ c=[2, 3, 4] $ (as in the sample). Examples of arrays $ a $ that are not good: - $ a = [3, 2, 3] $ is not good because $ a_1 > c_1 $ ; - $ a = [0, -1, 3] $ is not good because $ a_2 < 0 $ . One possible good array $ a $ is $ [0, 2, 4] $ . We can show that no operation has any effect on this array, so $ F(a, b) = a_1 = 0 $ . Another possible good array $ a $ is $ [0, 1, 4] $ . In a single operation with $ i = 1 $ , we set $ a_1 = \min(\frac{0+1-2}{2}, 0) $ and $ a_2 = \max(\frac{0+1+2}{2}, 1) $ . So, after a single operation with $ i = 1 $ , $ a $ becomes equal to $ [-\frac{1}{2}, \frac{3}{2}, 4] $ . We can show that no operation has any effect on this array, so $ F(a, b) = -\frac{1}{2} $ .