P5579 [PA 2015] Haystacks

Farmer Byteasar bought a piece of land with area $n$ mu, and he wants to grow grass on it. On each mu of land, he plants a unique type of grass. The grass on the $i$-th mu grows by $a_i$ centimeters every day. Byteasar will harvest $m$ times. The $i$-th harvest happens on day $d_i$, and he cuts off all parts whose height is greater than or equal to $b_i$. Byteasar wants to know, for each harvest, what the total height of grass obtained is. Can you help him?

The first line contains two positive integers $n, m$, representing the number of mu and the number of harvests. The second line contains $n$ positive integers. The $i$-th number is $a_i$, describing the growth rate of the grass on each mu. In the next $m$ lines, each line contains two integers $d_i, b_i$, describing each harvest in order.

Output $m$ lines. Each line contains one integer, answering in order the total height of grass obtained in each harvest.

For $100\%$ of the testdata, $1 \le n, m \le 5 \times 10^5$, $1 \le a_i \le 10^6$, $1 \le d_i \le 10^{12}$, $0 \le b_i \le 10^{12}$. The testdata guarantees that $d_1 < d_2 < \dots < d_m$, and at any time, the height of the grass on any mu never exceeds $10^{12}$. Translated by ChatGPT 5