\(4^{th}\) round, January \(19^{th}\), 2013

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-co\)ordinate of 0, and the right wall
has the \(x-co\)ordinate of \(N - 1\). Each integ\(er-va\)lued \(x-co\)ordinate of the aquarium bottom (let us denote
it by i) from 0 to \(N - 1\) has a separately adjustable height of H_{i}. Between any two adjacent integer-
valued \(x-co\)ordinates i and \(i + 1\), the bottom can be described by a line segment between points (i, H_{i})
and (\(i + 1\), H_{i}_{+ 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 \le N \le 100\,000\), the length of the bottom)
and M (\(1 \le M \le 100\,000\), the number of queries).
The second line of input contains N spa\(ce-se\)parated nonnegative integers H_{i} (\(0 \le H_{i} \le 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 \le h \le 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-co\)ordinate i (\(0 \le i \le N - 1\)) to h (\(0 \le h\) ≤
1000); in other words, set \(H_{i} = 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.

\(4^{th}\) round, January \(19^{th}\), 2013

생성자가 기록되지 않았습니다.

출처 COCI 2012/2013 Contest 4