COCI 2012/2013 contest4-6 , 번역 : functionx 2013.02.23 모의테스트5- 화면 보호기(AKVARIJ) > 문제은행 : 정보올림피아드&알고리즘




1632 : 화면 보호기(AKVARIJ)

제한시간
1000 ms   
메모리제한
256 MB   
해결횟수
6 회   
시도횟수
12 회   

문제

미르코는 새로운 화면 보호기를 설치하였다. 

미르코가 5분 동안 가만히 있으면 화면은 물고기가 움직이는 수족관을 보여준다. 

이 화면 보호기에서는 수족관의 바닥과 수위를 조절할 수 있다.


수족관을 좌표 평면상에 나타내면, 왼쪽 벽의 x 좌표는 0이고 오른쪽 벽의 x 좌표는 N-1이다. 

또, 수족관의 바닥은 (0, H0), (1, H1), …, (k, Hk), …, (N, HN-1)을 순서대로 연결하는 꺾은선 그래프 모양이다.


수족관의 수위가 h인 경우에는, y좌표가 0~h 범위 내에서 전부 물로 채워진다.(바닥에 해당되는 곳 제외) 

만약 수족관의 수위가 바닥보다 낮은 경우에는 바닥이 전부 물에 잠기지 않고 섬이 형성될 것이다.

 


미르코를 도와, 바닥과 수위를 조절할 때 물이 차지하는 영역의 넓이를 구하는 프로그램을 작성하여라.

 

 

[예제 3번 보충설명]

왼쪽 그림은 3번 예제 초기 상태이다. 오른쪽 그림은 U 로 시작하는 명령을 실행한 후의 상태이다.

 


 


입력형식

첫 번째 줄에는 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" 이다.


입력 예

3 2
20 20 20
Q 20
Q 30

출력 예

0.000
20.000

입력 예

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

출력 예

2.000 
1.000 
2.500

입력 예

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

출력 예

0.750
3.750
9.000
1.500
6.000
12.000


segment tree, Fenwick, BIT

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP