409768: GYM103736 I IHI's Homework

IHI's assignment today is to solve inequality. His task is to calculate the number of solutions of the inequality $$$x_1+x_2+...+x_n\le s$$$.

To exercise IHI's ability to draw inferences from one another, the teacher gave each $$$x_i$$$ a limit. Each $$$x_i$$$ should be greater than or equal to $$$a_i$$$. In other words, $$$\forall x_i \ge a_i(1\le i \le n)$$$.

The teacher assigned a total of $$$q$$$ problems. For each of them, you are given two integers $$$x$$$ and $$$val$$$. You need to change the value of $$$a_x$$$ to $$$val$$$. In other words, each times, $$$a_x = val$$$. Then calculate the answer. Since this number may be very large, the teacher asks IHI to find the number modulo $$$(10^9 + 7)$$$.

Can you help IHI?

The first line of input contains three space-separated integers $$$n$$$, $$$s$$$ and $$$q$$$ $$$(1\le n \le 2\times{10}^{5}$$$, $$$0\le s \le2\times{10}^{5}$$$, $$$1\le q\le2\times10^{5})$$$ —— the length of the array $$$a$$$, the right value of the inequality, and the number of operations.

The second line contains $$$n$$$ space-separated integers $$$a_1,a_2,\cdots,a_n$$$ $$$(0\le a_i\le 2\times10^{5})$$$

The next $$$q$$$ lines contains two integers $$$x$$$ and $$$val (1\le x \le n$$$, $$$0\le val\le 2\times10^{5})$$$ —— You need to change $$$a_x$$$ to $$$val$$$.

Note that each operation permanently changes array $$$a$$$. In other words, $$$a_x$$$ will be forever changed.

Print $$$q$$$ integers. The $$$i$$$-th line is the answer to this problem after the $$$i$$$-th operation.

3 5 4
1 1 1
1 1
1 2
2 2
3 2

10
4
1
0

After the first operation ,$$$a$$$=$$$[1,1,1]$$$.The value of $$$ \{ x_1 , x_2 , x_3 \}$$$ can be $$$\{ 1,1,1\}$$$, $$$\{ 1,1,2\}$$$, $$$\{ 1,2,1\}$$$, $$$\{ 2,1,1\}$$$, $$$\{ 2,2,1\}$$$, $$$\{ 2,1,2\}$$$, $$$\{ 1,2,2\}$$$, $$$\{ 3,1,1\}$$$, $$$\{ 1,3,1\}$$$, $$$\{ 1,1,3\}$$$.So there are $$$10$$$ solutions, output $$$10$$$.

After the third operation,$$$a=[2,2,1]$$$.There's only one set of solution satisfies the inequality.——The value of$$$\{x_1,x_2,x_3\}=\{2,2,1\}.$$$

After the fourth operation,$$$a=[2,2,2]$$$,No set of solutions satisfies the inequality, so the output is $$$0$$$.