문제
미르코는 새로운 화면 보호기를 설치하였다.
미르코가 5분 동안 가만히 있으면 화면은 물고기가 움직이는 수족관을 보여준다.
이 화면 보호기에서는 수족관의 바닥과 수위를 조절할 수 있다.
수족관을 좌표 평면상에 나타내면, 왼쪽 벽의 x 좌표는 0이고 오른쪽 벽의 x 좌표는 N-1이다.
또, 수족관의 바닥은 (0, H0), (1, H1), …, (k, Hk), …, (N-1, HN-1)을 순서대로 연결하는 꺾은선 그래프 모양이다.
수족관의 수위가 h인 경우에는, y좌표가 0~h 범위 내에서 전부 물로 채워진다.(바닥에 해당되는 곳 제외)
만약 수족관의 수위가 바닥보다 낮은 경우에는 바닥이 전부 물에 잠기지 않고 섬이 형성될 것이다.
미르코를 도와, 바닥과 수위를 조절할 때 물이 차지하는 영역의 넓이를 구하는 프로그램을 작성하여라.
입력
첫 번째 줄에는 N, M이 주어진다. (3 ≤ N ≤ 100,000, 1 ≤ M ≤ 100,000)
두 번째 줄에는 N개의 정수 H0, H1, …, HN-1가 주어진다. (0 ≤ Hk≤ 1,000)
세 번째 줄부터 M개의 줄에는 다음 두 가지 명령 중 하나가 주어진다.
Q h - 수위가 h (0 ≤ h ≤ 1,000) 인 경우, 물이 차지하는 영역의 넓이를 구하는 명령
U k h - Hk를 h로 바꾸는 명령(0 ≤ h ≤ 1,000)
출력
각 Q 명령에 대해 물이 차지하는 영역의 넓이를 소수점 넷째 자리에서 반올림하여 셋째 자리까지 출력한다.
결과는 long double자료형으로 출력되어야 한다. 서식문자는 "%Lf" 이다.
예제1
32
202020
Q20
Q30
0.000
20.000
예제2
35
020
Q2
U11
Q1
U110
Q5
2.000
1.000
2.500
예제3
77
0213210
Q1
Q2
Q3
U30
Q1
Q2
Q3
0.750
3.750
9.000
1.500
6.000
12.000
왼쪽 그림은 3번 예제 초기 상태이다. 오른쪽 그림은 U 로 시작하는 명령을 실행한 후의 상태이다.
