수족관

프로그램 명: coci_akvarij(special judge)

제한시간: 1 초

[요약 중] xi 부터의 높이가 주어진다. 그 후 해당 질의 높이 아래에 있는 영역의 넓이를 구하는 것이 문제이다.

마지막 입출력 예시에서

7 7 
0 2 1 3 2 1 0 
Q 1 
Q 2 
Q 3 
U 3 0 
Q 1 
Q 2 
Q 3

입곱개의 xi(0 ~6) 까지의 높이가 주어지고 7 개의 질의.

초기 높이는 0 2 1 3 2 1 0

Q 1 은 높이 1 아래에 있는 색칠한 넓이

Q 2 는 높이 2 아래에 있는 색칠한 넓이

단 , 초기에 주어진 높이를 다음 명령으로 변경 가능하다.

U 3 0

x3 의 높이를 0 으로 변경하는 것이다.

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.

입출력 예

input 

3 2 
20 20 20 
Q 20 
Q 30 

output 

0.000 
20.000 

input 

3 5 
0 2 0 
Q 2 
U 1 1 
Q 1 
U 1 10 
Q 5 

output 

2.000 
1.000 
2.500 

input 

7 7 
0 2 1 3 2 1 0 
Q 1 
Q 2 
Q 3 
U 3 0 
Q 1 
Q 2 
Q 3 

output 

0.750 
3.750 
9.000 
1.500 
6.000 
12.000 

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.

출처:coci/2012-2013/contest4

[질/답] [제출 현황] [푼 후(0)]

[ 채 점 ] [홈으로] [뒤 로]