P5874 [IOI 2015] horses

Like his ancestors, Mansur enjoys breeding horses. He currently owns the largest horse ranch in Kazakhstan. It was not always like this: $N$ years ago, when Mansur was young, he only owned one horse, but he kept dreaming of becoming rich, and in the end his dream came true. Number the years in chronological order from $0$ to $N-1$ (that is, year $N-1$ is the most recent year). Each year’s weather affects horse breeding. Mansur records a positive integer $X[i]$ as the breeding factor of year $i$. If there are $h$ horses at the beginning of year $i$, then there will be $h \times X[i]$ horses at the end of that year. Each year, horses can only be sold at the end of the year. Mansur records a positive integer $Y[i]$ as the price for selling one horse at the end of year $i$. Mansur may sell any number of horses, and each horse is sold for $Y[i]$. Now, Mansur wants to know: over these $N$ years, if he always sells horses at the best time, what is the maximum total revenue he can obtain? You happen to be visiting Mansur’s home, so he asks you to help answer this question. Mansur performed $M$ updates to the recorded arrays $X$ and $Y$. In each update, Mansur either changes one $X[i]$ or changes one $Y[i]$. After each update, he asks you again for the maximum revenue from selling horses. Mansur’s updates are cumulative, meaning each answer should take into account all previous updates. Note that some $X[i]$ or $Y[i]$ may be updated multiple times. The real answer to Mansur’s question may be extremely large. You only need to output the real answer modulo $10^9+7$.

- Line $1$: An integer $N$, the total number of years. - Line $2$: $N$ positive integers $X[0],\cdots,X[N - 1]$. For $0\le i \le N-1$, $X[i]$ is the breeding factor of year $i$. - Line $3$: $N$ positive integers $Y[0],\cdots,Y[N - 1]$. For $0\le i \le N-1$, $Y[i]$ is the price of selling one horse at the end of year $i$. - Line $4$: An integer $M$, the number of updates. - Lines $5$ to $M+4$: Each line contains three numbers $type$, $pos$, $val$ ($type=1$ means changing $X[ pos ]$ to $val$, $type=2$ means changing $Y[ pos ]$ to $val$).

- A total of $M+1$ lines. - Line $1$: One integer, the maximum revenue in the initial state modulo $10^9+7$. - Lines $2$ to $M+1$: One integer per line, the maximum revenue after this update modulo $10^9+7$.

Constraints: for $100\%$ of the data, $1\le N\le 5\times 10^5$, $0 \le M \le 10^5$. Translated by ChatGPT 5