시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 159 30 18 60.000%

문제

상근이는 새 화면 보호기를 설치했다. 컴퓨터를 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+XHJcblxyXG48cD5cdWMyMThcdWM4NzFcdWFkMDBcdWM3NDAgXHViMTA4XHViZTQ0XHVhYzAwIE4tMVx1Yzc3OCAyXHVjYzI4XHVjNmQwIFx1ZDNjOVx1YmE3NFx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHViNTRjLCBOXHVjNzQwIFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuIFx1YzIxOFx1Yzg3MVx1YWQwMFx1Yzc1OCBcdWFjMDBcdWM3YTUgXHVjNjdjXHVjYWJkIHhcdWM4OGNcdWQ0NWNcdWIyOTQgMFx1Yzc3NFx1YWNlMCwgXHVhYzAwXHVjN2E1IFx1YzYyNFx1Yjk3OFx1Y2FiZCB4XHVjODhjXHVkNDVjXHViMjk0IE4tMVx1Yzc3NFx1YjJlNC4gXHVhYzAxIFx1YzgxNVx1YzIxOCB4XHVjODhjXHVkNDVjIGlcdWIyOTQgXHViYzE0XHViMmU1XHVjNzU4IFx1YjE5Mlx1Yzc3NCBIPHN1Yj5pPFwvc3ViPlx1Yjk3YyBcdWFjMTZcdWIyOTRcdWIyZTQuIFx1Yzc3NCBcdWIxOTJcdWM3NzRcdWIyOTQgXHVjMTI0XHVjODE1XHVjNWQwXHVjMTFjIFx1YmMxNFx1YWZjMCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWJjMTRcdWIyZTVcdWM3NDAgXHVjNzc4XHVjODExXHVkNTVjIFx1YjQ1MCB4XHVjODhjXHVkNDVjIGlcdWM2NDAgaSsxXHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyAoaSwgSDxzdWI+aTxcL3N1Yj4pXHVjNjQwIChpKzEsIEg8c3ViPmkrMTxcL3N1Yj4pXHVjNzQ0IFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWMxMjBcdWJkODRcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzIxOFx1YmE3NFx1Yzc1OCBcdWIxOTJcdWM3NzRcdWFjMDAgaFx1Yjc3Y1x1YmE3NCwgXHVjMjE4XHVjODcxXHVhZDAwXHVjNzU4IFx1YmMxNFx1YjJlNVx1YWNmYyB5PWggXHVjMGFjXHVjNzc0XHVjNzU4IFx1YmFhOFx1YjRlMCBcdWFjZjVcdWFjMDRcdWM3NzQgXHViYjNjXHViODVjIFx1Y2M0NFx1YzZjY1x1YzljMFx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1YjljY1x1YzU3ZCwgaFx1YmNmNFx1YjJlNCBcdWIxOTJcdWM3NDAgXHViYzE0XHViMmU1XHVjNzc0IFx1Yzc4OFx1YjJlNFx1YmE3NCwgXHVhZGY4IFx1YWNmM1x1Yzc0MCBcdWMxMmNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWMxMjRcdWM4MTVcdWM1ZDBcdWMxMWMgXHVjMjE4XHVjODcxXHVhZDAwIFx1YmMxNFx1YjJlNSBcdWM4OGNcdWQ0NWNcdWM2NDAgXHVjMjE4XHViYTc0XHVjNzU4IFx1YjE5Mlx1Yzc3NFx1Yjk3YyBcdWJjMTRcdWFmYzAgXHViNTRjIFx1YjljOFx1YjJlNCBcdWJiM2NcdWI4NWMgXHVjYzQ0XHVjNmNjXHVjOWMwXHViMjk0IFx1YWNmM1x1Yzc1OCBcdWIxMTNcdWM3NzRcdWI5N2MgXHVhZDZjXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViNDUwIFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggTlx1YWNmYyBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVjMTI0XHVjODE1XHVjNzQ0IFx1YmMxNFx1YWZiYyBcdWQ2OWZcdWMyMTggTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgzICZsZTsgTiAmbGU7IDEwMCwwMDAsIDEgJmxlOyBNICZsZTsgMTAwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBOXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCBcdWJjMTRcdWIyZTVcdWM3NTggXHVjZDA4XHVhZTMwIFx1YjE5Mlx1Yzc3NCBIaVx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDAgJmxlOyBIaSAmbGU7IDEwMDApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBNXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVjMTI0XHVjODE1XHVjNWQwXHVjMTFjIFx1YmIzNFx1YzVjN1x1Yzc0NCBcdWJjMTRcdWFmYjhcdWM1YzhcdWIyOTQgXHVjOWMwXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+USBoXHViMjk0IFx1YzIxOFx1YmE3NFx1Yzc1OCBcdWIxOTJcdWM3NzRcdWI5N2MgaFx1Yjg1YyBcdWJjMTRcdWFmYjhcdWM1YzhcdWIyZTRcdWIyOTQgXHViNzNiXHVjNzc0XHViMmU0LiAoMCAmbGU7IGggJmxlOyAxMDAwKTxcL3A+XHJcblxyXG48cD5VIGkgaFx1YjI5NCB4XHVjODhjXHVkNDVjXHVhYzAwIGlcdWM3NzggXHVhY2YzXHVjNzU4IFx1YmMxNFx1YjJlNVx1Yzc1OCBcdWIxOTJcdWM3NzRcdWI5N2MgaFx1Yjg1YyBcdWJjMTRcdWFmYjhcdWM1YzhcdWIyZTRcdWIyOTQgXHViNzNiXHVjNzc0XHViMmU0LiAoMCAmbGU7IGkgJmxlOyBOLTEsIDAgJmxlOyBoICZsZTsgMTAwMCkgXHVjOTg5LCBIaSA9IGg8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5RXHViODVjIFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YjI5NCBcdWJjYzBcdWFjYmRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM4IFx1YjU0YyBcdWI5YzhcdWIyZTQsIFx1YmIzY1x1Yjg1YyBcdWNjNDRcdWM2Y2NcdWM5YzBcdWIyOTQgXHVhY2YzXHVjNzU4IFx1YjExM1x1Yzc3NFx1Yjk3YyBcdWMxOGNcdWMyMThcdWM4MTAgXHVjMTRiXHVjOWY4IFx1Yzc5MFx1YjlhY1x1YWU0Y1x1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YzY3Y1x1Y2FiZCBcdWFkZjhcdWI5YmNcdWM3NDAgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGNcdWM3NTggXHVjMGMxXHVkMGRjXHVjNzc0XHViYTcwLCBcdWM2MjRcdWI5NzhcdWNhYmQgXHVhZGY4XHViOWJjXHVjNzQwIFVcdWI4NWMgXHVjMmRjXHVjNzkxXHVkNTU4XHViMjk0IFx1YzEyNFx1YzgxNSZuYnNwO1x1YmNjMFx1YWNiZFx1Yzc0NCBcdWMyMThcdWQ1ODlcdWQ1NWMgXHViNGE0XHVjNzU4IFx1YmFhOFx1YzJiNVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9zc2QucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjA5cHg7IHdpZHRoOjY2OHB4XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzOTkwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQUtWQVJJSiIsImRlc2NyaXB0aW9uIjoiPHA+TWlya28gaGFzIHJlY2VudGx5IGluc3RhbGxlZCBhIG5ldyBzY3JlZW5zYXZlci4gSWYgaGUgaXMgYXdheSBmcm9tIHRoZSBrZXlib2FyZCBmb3IgZml2ZSBtaW51dGVzLCB0aGUgc2NyZWVuIHNob3dzIGEgcGljdHVyZSBvZiBhbiBhcXVhcml1bSB3aXRoIGFuaW1hdGVkIGZpc2guIFRoZSBzY3JlZW5zYXZlciBoYXMgc2V0dGluZ3MgZm9yIGN1c3RvbWl6aW5ndGhlIHNoYXBlIG9mIHRoZSAodmlydHVhbCwgc2FuZHkpIGFxdWFyaXVtIGJvdHRvbSwgYXMgd2VsbCBhcyB0aGUgd2F0ZXIgbGV2ZWwuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBhcXVhcml1bSBjYW4gYmUgcmVwcmVzZW50ZWQgaW4gYSAyRCBDYXJ0ZXNpYW4gY29vcmRpbmF0ZSBzeXN0ZW0gYXMgYSBzaGFwZSBOIC0gMSBjb2x1bW5zIHdpZGUsIHdoZXJlIE4gaXMgYSBwb3NpdGl2ZSBpbnRlZ2VyLiBUaGUgbGVmdCB3YWxsIG9mIHRoZSBhcXVhcml1bSBoYXMgdGhlIHgtY29vcmRpbmF0ZSBvZiAwLCBhbmQgdGhlIHJpZ2h0IHdhbGwgaGFzIHRoZSB4LWNvb3JkaW5hdGUgb2YgTiAtIDEuIEVhY2ggaW50ZWdlci12YWx1ZWQgeC1jb29yZGluYXRlIG9mIHRoZSBhcXVhcml1bSBib3R0b20gKGxldCB1cyBkZW5vdGUgaXQgYnkgaSkgZnJvbSAwIHRvIE4gLSAxIGhhcyBhIHNlcGFyYXRlbHkgYWRqdXN0YWJsZSBoZWlnaHQgb2YgSDxzdWI+aTxcL3N1Yj4uIEJldHdlZW4gYW55IHR3byBhZGphY2VudCBpbnRlZ2VydmFsdWVkIHgtY29vcmRpbmF0ZXMgaSBhbmQgaSArIDEsIHRoZSBib3R0b20gY2FuIGJlIGRlc2NyaWJlZCBieSBhIGxpbmUgc2VnbWVudCBiZXR3ZWVuIHBvaW50cyAoaSwgSDxzdWI+aTxcL3N1Yj4pIGFuZCAoaSArIDEsIEg8c3ViPmkgKyAxPFwvc3ViPikuJm5ic3A7PFwvcD5cclxuXHJcbjxwPklmIHRoZSB3YXRlciBsZXZlbCBpcyBzZXQgdG8gaCwgdGhlIHdhdGVyIGZpbGxzIHRoZSBhcmVhIGJldHdlZW4gdGhlIGxpbmUgeSA9IGggYW5kIHRoZSBhcXVhcml1bSBib3R0b20uIElmIGEgcGFydCBvZiB0aGUgYXF1YXJpdW0gYm90dG9tIGlzIGFib3ZlIHRoZSB3YXRlciBsZXZlbCBoLCBpdCBmb3JtcyBhbiBpc2xhbmQgYW5kIGlzIG5vdCBzdWJtZXJnZWQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZvciBkaWZmZXJlbnQgc2hhcGVzIG9mIHRoZSBhcXVhcml1bSBib3R0b20sIE1pcmtvIHdvdWxkIGxpa2UgdG8ga25vdyB0aGUgdG90YWxhcmVhIG9mIGhpcyBzY3JlZW4gY292ZXJlZCBieSB3YXRlci4gSGVscCBNaXJrbyBmaW5kIGFuc3dlcnMgdG8gaGlzIHF1ZXN0aW9ucyAob3RoZXIgdGhhbiA0MikuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0d28gcG9zaXRpdmUgaW50ZWdlcnMsIE4gKDMgJmxlOyBOICZsZTsgMTAwIDAwMCwgdGhlIGxlbmd0aCBvZiB0aGUgYm90dG9tKSBhbmQgTSAoMSAmbGU7IE0gJmxlOyAxMDAgMDAwLCB0aGUgbnVtYmVyIG9mIHF1ZXJpZXMpLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgb2YgaW5wdXQgY29udGFpbnMgTiBzcGFjZS1zZXBhcmF0ZWQgbm9ubmVnYXRpdmUgaW50ZWdlcnMgSDxzdWI+aTxcL3N1Yj4gKDAgJmxlOyBIPHN1Yj5pPFwvc3ViPiAmbGU7IDEwMDApLCB0aGUgc3RhcnRpbmcgYm90dG9tIGhlaWdodHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBNIGxpbmVzIGNvbnRhaW5zIGEgc2luZ2xlIHF1ZXJ5IHdpdGggb25lIG9mIHRoZSBmb2xsb3dpbmcgdHdvIHR5cGVzOiZuYnNwOzxcL3A+XHJcblxyXG48cD5RIGggJm5kYXNoOyBpZiB0aGUgd2F0ZXIgbGV2ZWwgaXMgc2V0IHRvIGggKDAgJmxlOyBoICZsZTsgMTAwMCksIGFzc3VtaW5nIHRoZSBjdXJyZW50IGJvdHRvbSBzaGFwZSwgd2hhdCBpcyB0aGUgdG90YWwgc2NyZWVuIGFyZWEgY292ZXJlZCBieSB3YXRlcj8mbmJzcDs8XC9wPlxyXG5cclxuPHA+VSBpIGggJm5kYXNoOyBNaXJrbyBoYXMgZGVjaWRlZCB0byBjaGFuZ2UgdGhlIGJvdHRvbSBoZWlnaHQgYXQgeC1jb29yZGluYXRlIGkgKDAgJmxlOyBpICZsZTsgTiAtIDEpIHRvIGggKDAgJmxlOyBoICZsZTsgMTAwMCk7IGluIG90aGVyIHdvcmRzLCBzZXQgSDxzdWI+aTxcL3N1Yj4gPSBoPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+b3IgZWFjaCBxdWVyeSB3aXRoIHR5cGUgUSwgb3V0cHV0IGEgc2luZ2xlIGxpbmUgY29udGFpbmluZyB0aGUgcmVxdWlyZWQgYXJlYSwgcm91bmRlZCB0byBleGFjdGx5IHRocmVlIGRlY2ltYWxzLiBUaGUgYXJlYSBnaXZlbiBpcyBhbGxvd2VkIHRvIGRpZmZlciBieSBhdCBtb3N0IDAuMDAxIGZyb20gdGhlIG9mZmljaWFsIHNvbHV0aW9uLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiI8cD5UaGUgbGVmdCBpbWFnZSBiZWxvdyBzaG93cyB0aGUgc2l0dWF0aW9uIGJlZm9yZSwgYW5kIHRoZSByaWdodCBvbmUgYWZ0ZXIgdGhlIFUtdHlwZSBxdWVyeSwgZm9yIHdhdGVyIGxldmVsIGggPSAyIChxdWVyeSBRIDIpLiBJbiB0aGUgZmlyc3QgaW1hZ2UsIHRoZSBzdWJtZXJnZWQgYXJlYSBlcXVhbHMgMy43NSwgYW5kIGluIHRoZSBzZWNvbmQgaW1hZ2UgaXQgaXMgNi48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9zc2QucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjA5cHg7IHdpZHRoOjY2OHB4XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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

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