시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 143 22 15 62.500%

문제

상근이는 새 화면 보호기를 설치했다. 컴퓨터를 5분동안 사용하지 않으면 화면 보호기가 실행된다. 이 화면 보호기는 수족관 그림과 움직이는 물고기를 보여준다. 화면 보호기 설정 화면에서는 바닥의 모양과 수면의 높이를 설정할 수 있다.

수족관은 너비가 N-1인 2차원 평면으로 나타낼 수 있다. 이 때, N은 양의 정수이다. 수족관의 가장 왼쪽 x좌표는 0이고, 가장 오른쪽 x좌표는 N-1이다. 각 정수 x좌표 i는 바닥의 높이 Hi를 갖는다. 이 높이는 설정에서 바꿀 수 있다. 바닥은 인접한 두 x좌표 i와 i+1를 이용해서 (i, Hi)와 (i+1, Hi+1)을 연결하는 선분으로 나타낼 수 있다.

수면의 높이가 h라면, 수족관의 바닥과 y=h 사이의 모든 공간이 물로 채워지게 된다. 만약, h보다 높은 바닥이 있다면, 그 곳은 섬이다.

상근이는 설정에서 수족관 바닥 좌표와 수면의 높이를 바꿀 때 마다 물로 채워지는 곳의 넓이를 구하려고 한다.

입력

첫째 줄에 두 양의 정수 N과 상근이가 설정을 바꾼 횟수 M이 주어진다. (3 ≤ N ≤ 100,000, 1 ≤ M ≤ 100,000)

둘째 줄에는 N개의 정수 바닥의 초기 높이 Hi가 공백으로 구분되어 주어진다. (0 ≤ Hi ≤ 1000)

다음 M개 줄에는 상근이가 설정에서 무엇을 바꾸었는 지가 주어진다.

Q h는 수면의 높이를 h로 바꾸었다는 뜻이다. (0 ≤ h ≤ 1000)

U i h는 x좌표가 i인 곳의 바닥의 높이를 h로 바꾸었다는 뜻이다. (0 ≤ i ≤ N-1, 0 ≤ h ≤ 1000) 즉, Hi = h

출력

Q로 시작하는 변경이 주어질 때 마다, 물로 채워지는 곳의 넓이를 소수점 셋째 자리까지 출력한다.

예제 입력 1

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

예제 출력 1

0.750
3.750
9.000
1.500
6.000
12.000

힌트

왼쪽 그림은 입력으로 주어졌을 때의 상태이며, 오른쪽 그림은 U로 시작하는 설졍 변경을 수행한 뒤의 모습이다.

W3sicHJvYmxlbV9pZCI6IjM5OTAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ2NTRcdWJhNzQgXHViY2Y0XHVkNjM4XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjMGM4IFx1ZDY1NFx1YmE3NCBcdWJjZjRcdWQ2MzhcdWFlMzBcdWI5N2MgXHVjMTI0XHVjZTU4XHVkNTg4XHViMmU0LiBcdWNlZjRcdWQ0ZThcdWQxMzBcdWI5N2MgNVx1YmQ4NFx1YjNkOVx1YzU0OCBcdWMwYWNcdWM2YTlcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNzNjXHViYTc0IFx1ZDY1NFx1YmE3NCBcdWJjZjRcdWQ2MzhcdWFlMzBcdWFjMDAgXHVjMmU0XHVkNTg5XHViNDFjXHViMmU0LiBcdWM3NzQgXHVkNjU0XHViYTc0IFx1YmNmNFx1ZDYzOFx1YWUzMFx1YjI5NCBcdWMyMThcdWM4NzFcdWFkMDAgXHVhZGY4XHViOWJjXHVhY2ZjIFx1YzZjMFx1YzljMVx1Yzc3NFx1YjI5NCBcdWJiM2NcdWFjZTBcdWFlMzBcdWI5N2MgXHViY2Y0XHVjNWVjXHVjOTAwXHViMmU0LiBcdWQ2NTRcdWJhNzQgXHViY2Y0XHVkNjM4XHVhZTMwIFx1YzEyNFx1YzgxNSBcdWQ2NTRcdWJhNzRcdWM1ZDBcdWMxMWNcdWIyOTQgXHViYzE0XHViMmU1XHVjNzU4IFx1YmFhOFx1YzU5MVx1YWNmYyBcdWMyMThcdWJhNzRcdWM3NTggXHViMTkyXHVjNzc0XHViOTdjIFx1YzEyNFx1YzgxNVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG5cclxuXHJcbjxwPlx1YzIxOFx1Yzg3MVx1YWQwMFx1Yzc0MCBcdWIxMDhcdWJlNDRcdWFjMDAgTi0xXHVjNzc4IDJcdWNjMjhcdWM2ZDAgXHVkM2M5XHViYTc0XHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM3NzQgXHViNTRjLCBOXHVjNzQwIFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuIFx1YzIxOFx1Yzg3MVx1YWQwMFx1Yzc1OCBcdWFjMDBcdWM3YTUgXHVjNjdjXHVjYWJkIHhcdWM4OGNcdWQ0NWNcdWIyOTQgMFx1Yzc3NFx1YWNlMCwgXHVhYzAwXHVjN2E1IFx1YzYyNFx1Yjk3OFx1Y2FiZCB4XHVjODhjXHVkNDVjXHViMjk0IE4tMVx1Yzc3NFx1YjJlNC4gXHVhYzAxIFx1YzgxNVx1YzIxOCB4XHVjODhjXHVkNDVjIGlcdWIyOTQgXHViYzE0XHViMmU1XHVjNzU4IFx1YjE5Mlx1Yzc3NCBIPHN1Yj5pPFwvc3ViPlx1Yjk3YyBcdWFjMTZcdWIyOTRcdWIyZTQuIFx1Yzc3NCBcdWIxOTJcdWM3NzRcdWIyOTQgXHVjMTI0XHVjODE1XHVjNWQwXHVjMTFjIFx1YmMxNFx1YWZjMCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWJjMTRcdWIyZTVcdWM3NDAgXHVjNzc4XHVjODExXHVkNTVjIFx1YjQ1MCB4XHVjODhjXHVkNDVjIGlcdWM2NDAgaSsxXHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyAoaSwgSDxzdWI+aTxcL3N1Yj4pXHVjNjQwIChpKzEsIEg8c3ViPmkrMTxcL3N1Yj4pXHVjNzQ0IFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWMxMjBcdWJkODRcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcblxyXG5cclxuPHA+XHVjMjE4XHViYTc0XHVjNzU4IFx1YjE5Mlx1Yzc3NFx1YWMwMCBoXHViNzdjXHViYTc0LCBcdWMyMThcdWM4NzFcdWFkMDBcdWM3NTggXHViYzE0XHViMmU1XHVhY2ZjIHk9aCBcdWMwYWNcdWM3NzRcdWM3NTggXHViYWE4XHViNGUwIFx1YWNmNVx1YWMwNFx1Yzc3NCBcdWJiM2NcdWI4NWMgXHVjYzQ0XHVjNmNjXHVjOWMwXHVhYzhjIFx1YjQxY1x1YjJlNC4gXHViOWNjXHVjNTdkLCBoXHViY2Y0XHViMmU0IFx1YjE5Mlx1Yzc0MCBcdWJjMTRcdWIyZTVcdWM3NzQgXHVjNzg4XHViMmU0XHViYTc0LCBcdWFkZjggXHVhY2YzXHVjNzQwIFx1YzEyY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuXHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjMTI0XHVjODE1XHVjNWQwXHVjMTFjIFx1YzIxOFx1Yzg3MVx1YWQwMCBcdWJjMTRcdWIyZTUgXHVjODhjXHVkNDVjXHVjNjQwIFx1YzIxOFx1YmE3NFx1Yzc1OCBcdWIxOTJcdWM3NzRcdWI5N2MgXHViYzE0XHVhZmMwIFx1YjU0YyBcdWI5YzhcdWIyZTQgXHViYjNjXHViODVjIFx1Y2M0NFx1YzZjY1x1YzljMFx1YjI5NCBcdWFjZjNcdWM3NTggXHViMTEzXHVjNzc0XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjQ1MCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4IE5cdWFjZmMgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YzEyNFx1YzgxNVx1Yzc0NCBcdWJjMTRcdWFmYmMgXHVkNjlmXHVjMjE4IE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMyAmbGU7IE4gJmxlOyAxMDAsMDAwLCAxICZsZTsgTSAmbGU7IDEwMCwwMDApPFwvcD5cclxuXHJcblxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBOXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCBcdWJjMTRcdWIyZTVcdWM3NTggXHVjZDA4XHVhZTMwIFx1YjE5Mlx1Yzc3NCBIaVx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDAgJmxlOyBIaSAmbGU7IDEwMDApPFwvcD5cclxuXHJcblxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE1cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWMxMjRcdWM4MTVcdWM1ZDBcdWMxMWMgXHViYjM0XHVjNWM3XHVjNzQ0IFx1YmMxNFx1YWZiOFx1YzVjOFx1YjI5NCBcdWM5YzBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG5cclxuXHJcbjxwPlEgaFx1YjI5NCBcdWMyMThcdWJhNzRcdWM3NTggXHViMTkyXHVjNzc0XHViOTdjIGhcdWI4NWMgXHViYzE0XHVhZmI4XHVjNWM4XHViMmU0XHViMjk0IFx1YjczYlx1Yzc3NFx1YjJlNC4gKDAgJmxlOyBoICZsZTsgMTAwMCk8XC9wPlxyXG5cclxuXHJcblxyXG48cD5VIGkgaFx1YjI5NCB4XHVjODhjXHVkNDVjXHVhYzAwIGlcdWM3NzggXHVhY2YzXHVjNzU4IFx1YmMxNFx1YjJlNVx1Yzc1OCBcdWIxOTJcdWM3NzRcdWI5N2MgaFx1Yjg1YyBcdWJjMTRcdWFmYjhcdWM1YzhcdWIyZTRcdWIyOTQgXHViNzNiXHVjNzc0XHViMmU0LiAoMCAmbGU7IGkgJmxlOyBOLTEsIDAgJmxlOyBoICZsZTsgMTAwMCkgXHVjOTg5LCBIaSA9IGg8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5RXHViODVjIFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YjI5NCBcdWJjYzBcdWFjYmRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM4IFx1YjU0YyBcdWI5YzhcdWIyZTQsIFx1YmIzY1x1Yjg1YyBcdWNjNDRcdWM2Y2NcdWM5YzBcdWIyOTQgXHVhY2YzXHVjNzU4IFx1YjExM1x1Yzc3NFx1Yjk3YyBcdWMxOGNcdWMyMThcdWM4MTAgXHVjMTRiXHVjOWY4IFx1Yzc5MFx1YjlhY1x1YWU0Y1x1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YzY3Y1x1Y2FiZCBcdWFkZjhcdWI5YmNcdWM3NDAgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGNcdWM3NTggXHVjMGMxXHVkMGRjXHVjNzc0XHViYTcwLCBcdWM2MjRcdWI5NzhcdWNhYmQgXHVhZGY4XHViOWJjXHVjNzQwIFVcdWI4NWMgXHVjMmRjXHVjNzkxXHVkNTU4XHViMjk0IFx1YzEyNFx1Yzg0ZCBcdWJjYzBcdWFjYmRcdWM3NDQgXHVjMjE4XHVkNTg5XHVkNTVjIFx1YjRhNFx1Yzc1OCBcdWJhYThcdWMyYjVcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvc3NkLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIwOXB4OyB3aWR0aDo2NjhweFwiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzk5MCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkFLVkFSSUoiLCJkZXNjcmlwdGlvbiI6IjxwPk1pcmtvIGhhcyByZWNlbnRseSBpbnN0YWxsZWQgYSBuZXcgc2NyZWVuc2F2ZXIuIElmIGhlIGlzIGF3YXkgZnJvbSB0aGUga2V5Ym9hcmQgZm9yIGZpdmUgbWludXRlcywgdGhlIHNjcmVlbiBzaG93cyBhIHBpY3R1cmUgb2YgYW4gYXF1YXJpdW0gd2l0aCBhbmltYXRlZCBmaXNoLiBUaGUgc2NyZWVuc2F2ZXIgaGFzIHNldHRpbmdzIGZvciBjdXN0b21pemluZ3RoZSBzaGFwZSBvZiB0aGUgKHZpcnR1YWwsIHNhbmR5KSBhcXVhcml1bSBib3R0b20sIGFzIHdlbGwgYXMgdGhlIHdhdGVyIGxldmVsLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgYXF1YXJpdW0gY2FuIGJlIHJlcHJlc2VudGVkIGluIGEgMkQgQ2FydGVzaWFuIGNvb3JkaW5hdGUgc3lzdGVtIGFzIGEgc2hhcGUgTiAtIDEgY29sdW1ucyB3aWRlLCB3aGVyZSBOIGlzIGEgcG9zaXRpdmUgaW50ZWdlci4gVGhlIGxlZnQgd2FsbCBvZiB0aGUgYXF1YXJpdW0gaGFzIHRoZSB4LWNvb3JkaW5hdGUgb2YgMCwgYW5kIHRoZSByaWdodCB3YWxsIGhhcyB0aGUgeC1jb29yZGluYXRlIG9mIE4gLSAxLiBFYWNoIGludGVnZXItdmFsdWVkIHgtY29vcmRpbmF0ZSBvZiB0aGUgYXF1YXJpdW0gYm90dG9tIChsZXQgdXMgZGVub3RlIGl0IGJ5IGkpIGZyb20gMCB0byBOIC0gMSBoYXMgYSBzZXBhcmF0ZWx5IGFkanVzdGFibGUgaGVpZ2h0IG9mIEg8c3ViPmk8XC9zdWI+LiBCZXR3ZWVuIGFueSB0d28gYWRqYWNlbnQgaW50ZWdlcnZhbHVlZCB4LWNvb3JkaW5hdGVzIGkgYW5kIGkgKyAxLCB0aGUgYm90dG9tIGNhbiBiZSBkZXNjcmliZWQgYnkgYSBsaW5lIHNlZ21lbnQgYmV0d2VlbiBwb2ludHMgKGksIEg8c3ViPmk8XC9zdWI+KSBhbmQgKGkgKyAxLCBIPHN1Yj5pICsgMTxcL3N1Yj4pLiZuYnNwOzxcL3A+XHJcblxyXG48cD5JZiB0aGUgd2F0ZXIgbGV2ZWwgaXMgc2V0IHRvIGgsIHRoZSB3YXRlciBmaWxscyB0aGUgYXJlYSBiZXR3ZWVuIHRoZSBsaW5lIHkgPSBoIGFuZCB0aGUgYXF1YXJpdW0gYm90dG9tLiBJZiBhIHBhcnQgb2YgdGhlIGFxdWFyaXVtIGJvdHRvbSBpcyBhYm92ZSB0aGUgd2F0ZXIgbGV2ZWwgaCwgaXQgZm9ybXMgYW4gaXNsYW5kIGFuZCBpcyBub3Qgc3VibWVyZ2VkLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Gb3IgZGlmZmVyZW50IHNoYXBlcyBvZiB0aGUgYXF1YXJpdW0gYm90dG9tLCBNaXJrbyB3b3VsZCBsaWtlIHRvIGtub3cgdGhlIHRvdGFsYXJlYSBvZiBoaXMgc2NyZWVuIGNvdmVyZWQgYnkgd2F0ZXIuIEhlbHAgTWlya28gZmluZCBhbnN3ZXJzIHRvIGhpcyBxdWVzdGlvbnMgKG90aGVyIHRoYW4gNDIpLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIHBvc2l0aXZlIGludGVnZXJzLCBOICgzICZsZTsgTiAmbGU7IDEwMCAwMDAsIHRoZSBsZW5ndGggb2YgdGhlIGJvdHRvbSkgYW5kIE0gKDEgJmxlOyBNICZsZTsgMTAwIDAwMCwgdGhlIG51bWJlciBvZiBxdWVyaWVzKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIE4gc3BhY2Utc2VwYXJhdGVkIG5vbm5lZ2F0aXZlIGludGVnZXJzIEg8c3ViPmk8XC9zdWI+ICgwICZsZTsgSDxzdWI+aTxcL3N1Yj4gJmxlOyAxMDAwKSwgdGhlIHN0YXJ0aW5nIGJvdHRvbSBoZWlnaHRzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgTSBsaW5lcyBjb250YWlucyBhIHNpbmdsZSBxdWVyeSB3aXRoIG9uZSBvZiB0aGUgZm9sbG93aW5nIHR3byB0eXBlczombmJzcDs8XC9wPlxyXG5cclxuPHA+USBoICZuZGFzaDsgaWYgdGhlIHdhdGVyIGxldmVsIGlzIHNldCB0byBoICgwICZsZTsgaCAmbGU7IDEwMDApLCBhc3N1bWluZyB0aGUgY3VycmVudCBib3R0b20gc2hhcGUsIHdoYXQgaXMgdGhlIHRvdGFsIHNjcmVlbiBhcmVhIGNvdmVyZWQgYnkgd2F0ZXI/Jm5ic3A7PFwvcD5cclxuXHJcbjxwPlUgaSBoICZuZGFzaDsgTWlya28gaGFzIGRlY2lkZWQgdG8gY2hhbmdlIHRoZSBib3R0b20gaGVpZ2h0IGF0IHgtY29vcmRpbmF0ZSBpICgwICZsZTsgaSAmbGU7IE4gLSAxKSB0byBoICgwICZsZTsgaCAmbGU7IDEwMDApOyBpbiBvdGhlciB3b3Jkcywgc2V0IEg8c3ViPmk8XC9zdWI+ID0gaDxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPm9yIGVhY2ggcXVlcnkgd2l0aCB0eXBlIFEsIG91dHB1dCBhIHNpbmdsZSBsaW5lIGNvbnRhaW5pbmcgdGhlIHJlcXVpcmVkIGFyZWEsIHJvdW5kZWQgdG8gZXhhY3RseSB0aHJlZSBkZWNpbWFscy4gVGhlIGFyZWEgZ2l2ZW4gaXMgYWxsb3dlZCB0byBkaWZmZXIgYnkgYXQgbW9zdCAwLjAwMSBmcm9tIHRoZSBvZmZpY2lhbCBzb2x1dGlvbi4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHA+VGhlIGxlZnQgaW1hZ2UgYmVsb3cgc2hvd3MgdGhlIHNpdHVhdGlvbiBiZWZvcmUsIGFuZCB0aGUgcmlnaHQgb25lIGFmdGVyIHRoZSBVLXR5cGUgcXVlcnksIGZvciB3YXRlciBsZXZlbCBoID0gMiAocXVlcnkgUSAyKS4gSW4gdGhlIGZpcnN0IGltYWdlLCB0aGUgc3VibWVyZ2VkIGFyZWEgZXF1YWxzIDMuNzUsIGFuZCBpbiB0aGUgc2Vjb25kIGltYWdlIGl0IGlzIDYuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvc3NkLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIwOXB4OyB3aWR0aDo2NjhweFwiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Contest > Croatian Open Competition in Informatics > COCI 2012/2013 > Contest #4 6번