시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHJcblxyXG48cD5cdWMyMThcdWM4NzFcdWFkMDBcdWM3NDAgXHViMTA4XHViZTQ0XHVhYzAwIE4tMVx1Yzc3OCAyXHVjYzI4XHVjNmQwIFx1ZDNjOVx1YmE3NFx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YjU0YywgTlx1Yzc0MCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LiBcdWMyMThcdWM4NzFcdWFkMDBcdWM3NTggXHVhYzAwXHVjN2E1IFx1YzY3Y1x1Y2FiZCB4XHVjODhjXHVkNDVjXHViMjk0IDBcdWM3NzRcdWFjZTAsIFx1YWMwMFx1YzdhNSBcdWM2MjRcdWI5NzhcdWNhYmQgeFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCBOLTFcdWM3NzRcdWIyZTQuIFx1YWMwMSBcdWM4MTVcdWMyMTggeFx1Yzg4Y1x1ZDQ1YyBpXHViMjk0IFx1YmMxNFx1YjJlNVx1Yzc1OCBcdWIxOTJcdWM3NzQgSDxzdWI+aTxcL3N1Yj5cdWI5N2MgXHVhYzE2XHViMjk0XHViMmU0LiBcdWM3NzQgXHViMTkyXHVjNzc0XHViMjk0IFx1YzEyNFx1YzgxNVx1YzVkMFx1YzExYyBcdWJjMTRcdWFmYzAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViYzE0XHViMmU1XHVjNzQwIFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWI0NTAgeFx1Yzg4Y1x1ZDQ1YyBpXHVjNjQwIGkrMVx1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NzRcdWMxMWMgKGksIEg8c3ViPmk8XC9zdWI+KVx1YzY0MCAoaSsxLCBIPHN1Yj5pKzE8XC9zdWI+KVx1Yzc0NCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHVjMTIwXHViZDg0XHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMyMThcdWJhNzRcdWM3NTggXHViMTkyXHVjNzc0XHVhYzAwIGhcdWI3N2NcdWJhNzQsIFx1YzIxOFx1Yzg3MVx1YWQwMFx1Yzc1OCBcdWJjMTRcdWIyZTVcdWFjZmMgeT1oIFx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWJhYThcdWI0ZTAgXHVhY2Y1XHVhYzA0XHVjNzc0IFx1YmIzY1x1Yjg1YyBcdWNjNDRcdWM2Y2NcdWM5YzBcdWFjOGMgXHViNDFjXHViMmU0LiBcdWI5Y2NcdWM1N2QsIGhcdWJjZjRcdWIyZTQgXHViMTkyXHVjNzQwIFx1YmMxNFx1YjJlNVx1Yzc3NCBcdWM3ODhcdWIyZTRcdWJhNzQsIFx1YWRmOCBcdWFjZjNcdWM3NDAgXHVjMTJjXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjMTI0XHVjODE1XHVjNWQwXHVjMTFjIFx1YzIxOFx1Yzg3MVx1YWQwMCBcdWJjMTRcdWIyZTUgXHVjODhjXHVkNDVjXHVjNjQwIFx1YzIxOFx1YmE3NFx1Yzc1OCBcdWIxOTJcdWM3NzRcdWI5N2MgXHViYzE0XHVhZmMwIFx1YjU0YyBcdWI5YzhcdWIyZTQgXHViYjNjXHViODVjIFx1Y2M0NFx1YzZjY1x1YzljMFx1YjI5NCBcdWFjZjNcdWM3NTggXHViMTEzXHVjNzc0XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjQ1MCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4IE5cdWFjZmMgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YzEyNFx1YzgxNVx1Yzc0NCBcdWJjMTRcdWFmYmMgXHVkNjlmXHVjMjE4IE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMyAmbGU7IE4gJmxlOyAxMDAsMDAwLCAxICZsZTsgTSAmbGU7IDEwMCwwMDApPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgTlx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTggXHViYzE0XHViMmU1XHVjNzU4IFx1Y2QwOFx1YWUzMCBcdWIxOTJcdWM3NzQgSGlcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgwICZsZTsgSGkgJmxlOyAxMDAwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTVx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YzEyNFx1YzgxNVx1YzVkMFx1YzExYyBcdWJiMzRcdWM1YzdcdWM3NDQgXHViYzE0XHVhZmI4XHVjNWM4XHViMjk0IFx1YzljMFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlEgaFx1YjI5NCBcdWMyMThcdWJhNzRcdWM3NTggXHViMTkyXHVjNzc0XHViOTdjIGhcdWI4NWMgXHViYzE0XHVhZmI4XHVjNWM4XHViMmU0XHViMjk0IFx1YjczYlx1Yzc3NFx1YjJlNC4gKDAgJmxlOyBoICZsZTsgMTAwMCk8XC9wPlxyXG5cclxuPHA+VSBpIGhcdWIyOTQgeFx1Yzg4Y1x1ZDQ1Y1x1YWMwMCBpXHVjNzc4IFx1YWNmM1x1Yzc1OCBcdWJjMTRcdWIyZTVcdWM3NTggXHViMTkyXHVjNzc0XHViOTdjIGhcdWI4NWMgXHViYzE0XHVhZmI4XHVjNWM4XHViMmU0XHViMjk0IFx1YjczYlx1Yzc3NFx1YjJlNC4gKDAgJmxlOyBpICZsZTsgTi0xLCAwICZsZTsgaCAmbGU7IDEwMDApIFx1Yzk4OSwgSGkgPSBoPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UVx1Yjg1YyBcdWMyZGNcdWM3OTFcdWQ1NThcdWIyOTQgXHViY2MwXHVhY2JkXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljOCBcdWI1NGMgXHViOWM4XHViMmU0LCBcdWJiM2NcdWI4NWMgXHVjYzQ0XHVjNmNjXHVjOWMwXHViMjk0IFx1YWNmM1x1Yzc1OCBcdWIxMTNcdWM3NzRcdWI5N2MgXHVjMThjXHVjMjE4XHVjODEwIFx1YzE0Ylx1YzlmOCBcdWM3OTBcdWI5YWNcdWFlNGNcdWM5YzAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWM2N2NcdWNhYmQgXHVhZGY4XHViOWJjXHVjNzQwIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjXHVjNzU4IFx1YzBjMVx1ZDBkY1x1Yzc3NFx1YmE3MCwgXHVjNjI0XHViOTc4XHVjYWJkIFx1YWRmOFx1YjliY1x1Yzc0MCBVXHViODVjIFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YjI5NCBcdWMxMjRcdWM4MTUmbmJzcDtcdWJjYzBcdWFjYmRcdWM3NDQgXHVjMjE4XHVkNTg5XHVkNTVjIFx1YjRhNFx1Yzc1OCBcdWJhYThcdWMyYjVcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvc3NkLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIwOXB4OyB3aWR0aDo2NjhweFwiIFwvPjxcL3A+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번

  • 빠진 조건을 찾은 사람: august14
  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: ppp3195