A1485.[COCI-2012_2013-contest4]#1 AKVARIJ

Mirko has recently installed a new screensaver. If he is away from the keyboard for five minutes, the screen shows a picture of an aquarium with animated fish. The screensaver has settings for customizing the shape of the (virtual, sandy) aquarium bottom, as well as the water level.
The aquarium can be represented in a 2D Cartesian coordinate system as a shape N - 1 columns wide, where N is a positive integer. The left wall of the aquarium has the x-coordinate of 0, and the right wall has the x-coordinate of N -

1. Each integer-valued x-coordinate of the aquarium bottom (let us denote it by i) from 0 to N - 1 has a separately adjustable height of Hi . Between any two adjacent integervalued x-coordinates i and i + 1, the bottom can be described by a line segment between points (i, Hi)
   and (i + 1, Hi + 1).
   If the water level is set to h, the water fills the area between the line y = h and the aquarium bottom. If a part of the aquarium bottom is above the water level h, it forms an island and is not submerged.
   For different shapes of the aquarium bottom, Mirko would like to know the total area of his screen covered by water. Help Mirko find answers to his questions (other than 42).

The first line of input contains two positive integers, N (3 ≤ N ≤ 100 000, the length of the bottom)
and M (1 ≤ M ≤ 100 000, the number of queries).
The second line of input contains N space-separated nonnegative integers Hi (0 ≤ Hi ≤ 1000), the starting bottom heights.
Each of the following M lines contains a single query with one of the following two types:
Q h – if the water level is set to h (0 ≤ h ≤ 1000), assuming the current bottom shape, what is the total screen area covered by water?
U i h – Mirko has decided to change the bottom height at x-coordinate i (0 ≤ i ≤ N - 1) to h (0 ≤ h ≤
1000); in other words, set Hi = h.

For each query with type Q, output a single line containing the required area, rounded to exactly three decimals. The area given is allowed to differ by at most
0.001 from the official solution.

Clarification of the third example: The left image below shows the situation before, and the right
one after the U-type query, for water level h = 2 (query Q 2). In the first image, the submerged area
equals 3.75, and in the second image it is 6.