The area below the aquarium bottom consists of ~N-1~ trapezoids. We will find a way to calculate the area of one trapezoid and then improve it using data structures for faster work with all of them. For the sake of simplicity, we calculate the area of the unflooded part below the water level ~h~.

There are three cases for a trapezoid:

1. Water area is above the entire trapezoid.
2. Water area is below both upper vertices of the trapezoid.
3. Water area is between the upper vertices of the trapezoid.

In the first case, the area is equal to the area of the entire trapezoid.

In the second case, the area is equal to the water height ~h~.

In the third case, we calculate the area in the form ~A h^2 + B h + C~ (determining polynomial coefficients is left as an exercise to the reader).

In case there are more trapezoids, for a height ~h~ we can divide them into groups 1, 2, 3 above. From the first group we need the sum of all areas, from the second we need the number of trapezoids (the total area in this group is equal to ~h \times \text{number_of_trapezoids}~), and from the third we need the sum of corresponding polynomial coefficients, from which we can get a formula for the area of the group.

The problem is calculating the sum fast enough for each group. If for a given ~h~ we present each trapezoid as a point ~(H_i, H_{i+1})~, groups become rectangles as shown below:

Queries on such 2D intervals can be done using a 2D Fenwick tree. In each element of the structure, we store the sum of total areas, number of trapezoids and three sums of coefficients (~A~, ~B~ and ~C~). This structure is simply maintained when we change the height, and the complexity of a query is ~\mathcal O(\log^2 maxh)~. The total complexity of the algorithm is ~\mathcal O((N+M) \log^2 maxh)~.

There are alternative solutions. Instead of maintaining the structure of trapezoids, we can maintain the array of solutions for each ~h~. For each height, we are interested in the same three cases as before. If we have a trapezoid ~(H_i, H_{i+1})~ (for the sake of simplicity assume ~H_i \le H_{i+1}~), it contributes to the interval ~[0, H_i]~ with its total area, to the interval ~(H_i, H_{i+1})~ with its formula (see case 3), and to the interval ~[H_{i+1}, maxh]~ with increasing the number of trapezoids by ~1~. The array of solutions can once again be achieved as a Fenwick tree or a tournament tree and the complexity of an operation is then ~\mathcal O(\log maxh)~, in total ~\mathcal O(N \log maxh)~.