To solve the first subtask, we need to just calculate our answer using dynamic programming.

~dp[i][j]~ - what is the maximal profit if we pass ~i-1~ days and we have ~j~ horses, then we got ~j \times x_i~ horses and check all number of horses that we sell today and go to the next day.

Observation 1

First of all, let's consider two points ~i~ and ~j~. What if we sell ~k~ horses in the ~i^\text{th}~ and ~j^\text{th}~ day? And check which day is more profitable.

Profit of ~i^\text{th}~ day: ~x_1 \times x_2 \times \dots \times x_i \times y_i~

Profit of ~j^\text{th}~ day: ~x_1 \times x_2 \times \dots \times x_i \times x_{i+1} \times \dots \times x_j \times y_j~

It depends on this:

$$\displaystyle \begin{align*} y_i &\mathrel{?} x_{i+1} \times \dots \times x_j \times y_j \\ &> \\ &< \\ &= \end{align*}$$

• if it's ~>~ then it's more profitable to sell horses in ~i^\text{th}~ day
• if it's ~<~ then it's more profitable to sell horses in ~j^\text{th}~ day
• if it's ~=~ then it doesn't matter if we sell them in ~i^\text{th}~ day or in ~j^\text{th}~ day

From this point, it's clear that it is better to sell all our horses in one day that gives us maximal profit.

Using this observation, we can solve 2 subtasks.

After each query, we can solve the problem in ~\mathcal O(n)~.

Observation 2

If all ~x_i \ge 2~, then after ~30~ days, ~x_i \times x_{i+1} \times \dots \times x_{i+29} \ge 2^{30} > 10^9~, so position less than or equal ~n-30~ can never be an optimal solution, because even if ~y_n-30 = 10^9~ and ~y_n = 1~, ~2^{30} \times y_n > y_n-30~.

It's enough to check only the last ~30~ positions.

Observation 3

The main problem in the last subtask is ~x_i = 1~, but in that case, multiplication first ~x_i~ numbers and ~x_{i-1}~ is not changed. This allows us to merge consecutive positions with ~x_i = 1~. When we merge this position, we should take the maximal ~y_i~. So if we do that, it's enough to check the last ~60~ positions, because there can be no more than ~30~ merged ~1~'s between ~30~ last positions where ~x_i \ge 2~.

So we can store our state in some structure like set, that provides us information about current merged positions, and some structure that provides us RMQ. So solution per query will be ~\log(10^9) \log(n)~. Then to calculate the answer, we can use something like segment tree.

So overall complexity will be ~\mathcal O(m \log(10^9) \log(n))~.