시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 221 26 18 18.367%

문제

택희는 자료구조 수업시간에 다음과 같은 자료구조를 만들었다. 이 자료구조는 택희가 좋아하는 숫자 N개로 이루어진 수열에 아래와 같은 연산을 수행하는 것이다.

연산 형식 설명 예제
1 A B X A번째부터 B번째까지 수를 X로 바꾼다. (9,8,7,6,5,4,3,2,1) → 1 3 5 0 → (9,8,0,0,0,4,3,2,1)
2 A B X A번째 수에는 X를, A+1번째 수에는 2×X를, ..., B번째 수에는 (B-A+1)×X를 더한다. (9,8,7,6,5,4,3,2,1) → 2 3 5 2 → (9,8,9,10,11,4,3,2,1)
3 C X C번째 숫자 바로 앞에 X를 삽입한다. (9,8,7,6,5,4,3,2,1) → 3 4 100 → (9,8,7,100,6,5,4,3,2,1)
4 A B A번째 수부터 B번째 수를 더해서 출력한다. (2,18,7,6,1,4,7,7,2) → 4 6 7 → 결과: 11

택희가 좋아하는 숫자 N개로 이루어진 수열과 택희가 수행한 연산 목록이 주어졌을 때, 4번이 나올때 마다 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 Q가 주어진다. (1 ≤ N, Q ≤ 100,000) N은 처음 수열의 크기이고, Q는 택희가 수행한 연산의 개수이다.

둘째 줄에는 처음 수열이 주어진다. 수열의 수는 100,000을 넘지않는 음이 아닌 정수이며, 공백으로 구분되어져 있다.

셋째 줄부터 Q개의 줄에는 택희가 수행한 연산이 차례대로 주어진다. 0 ≤ X ≤ 100, 1 ≤ A ≤ B ≤ 현재 수열의 크기, 1 ≤ C ≤ 현재 수열의 크기+1

출력

4번 연산이 나올때 마다 합을 출력한다. 합이 32비트 정수를 넘어갈 수 있다.

예제 입력 1

5 5
1 2 3 4 5
1 5 5 0
4 4 5
4 5 5
2 1 5 1
4 1 5

예제 출력 1

4
0
25
W3sicHJvYmxlbV9pZCI6IjI4NDQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3OTBcdWI4Y2MgXHVhZDZjXHVjODcwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQwZGRcdWQ3NmNcdWIyOTQgXHVjNzkwXHViOGNjXHVhZDZjXHVjODcwIFx1YzIxOFx1YzVjNVx1YzJkY1x1YWMwNFx1YzVkMCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1Yzc5MFx1YjhjY1x1YWQ2Y1x1Yzg3MFx1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWM1YzhcdWIyZTQuIFx1Yzc3NCBcdWM3OTBcdWI4Y2NcdWFkNmNcdWM4NzBcdWIyOTQgXHVkMGRkXHVkNzZjXHVhYzAwIFx1Yzg4Ylx1YzU0NFx1ZDU1OFx1YjI5NCBcdWMyMmJcdWM3OTAgTlx1YWMxY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVjMjE4XHVjNWY0XHVjNWQwIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVjNWYwXHVjMGIwXHVjNzQ0IFx1YzIxOFx1ZDU4OVx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjx0YWJsZSBjbGFzcz1cInRhYmxlIHRhYmxlLWJvcmRlcmVkXCI+XHJcblx0PHRoZWFkPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ3aWR0aDoxMCU7XCI+XHVjNWYwXHVjMGIwIFx1ZDYxNVx1YzJkZDxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ3aWR0aDo0NSU7XCI+XHVjMTI0XHViYTg1PFwvdGQ+XHJcblx0XHRcdDx0ZCBzdHlsZT1cIndpZHRoOjQ1JTtcIj5cdWM2MDhcdWM4MWM8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3RoZWFkPlxyXG5cdDx0Ym9keT5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjEgQSBCIFg8XC90ZD5cclxuXHRcdFx0PHRkPkFcdWJjODhcdWM5ZjhcdWJkODBcdWQxMzAgQlx1YmM4OFx1YzlmOFx1YWU0Y1x1YzljMCBcdWMyMThcdWI5N2MgWFx1Yjg1YyBcdWJjMTRcdWFmYmNcdWIyZTQuPFwvdGQ+XHJcblx0XHRcdDx0ZD4oOSw4LDcsNiw1LDQsMywyLDEpJm5ic3A7JnJhcnI7Jm5ic3A7MSAzIDUgMCAmcmFycjsmbmJzcDsoOSw4LDxzdHJvbmc+MCwwLDAsPFwvc3Ryb25nPjQsMywyLDEpPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjIgQSBCIFg8XC90ZD5cclxuXHRcdFx0PHRkPkFcdWJjODhcdWM5ZjggXHVjMjE4XHVjNWQwXHViMjk0IFhcdWI5N2MsIEErMVx1YmM4OFx1YzlmOCBcdWMyMThcdWM1ZDBcdWIyOTQgMiZ0aW1lcztYXHViOTdjLCAuLi4sIEJcdWJjODhcdWM5ZjggXHVjMjE4XHVjNWQwXHViMjk0IChCLUErMSkmdGltZXM7WFx1Yjk3YyBcdWIzNTRcdWQ1NWNcdWIyZTQuPFwvdGQ+XHJcblx0XHRcdDx0ZD4oOSw4LDcsNiw1LDQsMywyLDEpJm5ic3A7JnJhcnI7Jm5ic3A7MiAzIDUgMiZuYnNwOyZyYXJyOyAoOSw4LDxzdHJvbmc+OSwxMCwxMSw8XC9zdHJvbmc+NCwzLDIsMSk8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+MyBDIFg8XC90ZD5cclxuXHRcdFx0PHRkPkNcdWJjODhcdWM5ZjggXHVjMjJiXHVjNzkwIFx1YmMxNFx1Yjg1YyBcdWM1NWVcdWM1ZDAgWFx1Yjk3YyBcdWMwYmRcdWM3ODVcdWQ1NWNcdWIyZTQuPFwvdGQ+XHJcblx0XHRcdDx0ZD4oOSw4LDcsNiw1LDQsMywyLDEpICZyYXJyOyZuYnNwOzMgNCAxMDAmbmJzcDsmcmFycjsgKDksOCw3LDxzdHJvbmc+MTAwLDxcL3N0cm9uZz42LDUsNCwzLDIsMSk8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+NCBBIEI8XC90ZD5cclxuXHRcdFx0PHRkPkFcdWJjODhcdWM5ZjggXHVjMjE4XHViZDgwXHVkMTMwIEJcdWJjODhcdWM5ZjggXHVjMjE4XHViOTdjIFx1YjM1NFx1ZDU3NFx1YzExYyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvdGQ+XHJcblx0XHRcdDx0ZD4oMiwxOCw3LDYsMSw0LDcsNywyKSZuYnNwOyZyYXJyOyZuYnNwOzQgNiA3ICZyYXJyOyZuYnNwO1x1YWNiMFx1YWNmYzogMTE8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3Rib2R5PlxyXG48XC90YWJsZT5cclxuXHJcbjxwPlx1ZDBkZFx1ZDc2Y1x1YWMwMCBcdWM4OGJcdWM1NDRcdWQ1NThcdWIyOTQgXHVjMjJiXHVjNzkwIE5cdWFjMWNcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YzIxOFx1YzVmNFx1YWNmYyBcdWQwZGRcdWQ3NmNcdWFjMDAgXHVjMjE4XHVkNTg5XHVkNTVjIFx1YzVmMFx1YzBiMCBcdWJhYTlcdWI4NWRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgNFx1YmM4OFx1Yzc3NCBcdWIwOThcdWM2MmNcdWI1NGMgXHViOWM4XHViMmU0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVhY2ZjIFFcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4sIFEgJmxlOyAxMDAsMDAwKSBOXHVjNzQwIFx1Y2M5OFx1Yzc0YyBcdWMyMThcdWM1ZjRcdWM3NTggXHVkMDZjXHVhZTMwXHVjNzc0XHVhY2UwLCBRXHViMjk0IFx1ZDBkZFx1ZDc2Y1x1YWMwMCBcdWMyMThcdWQ1ODlcdWQ1NWMgXHVjNWYwXHVjMGIwXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWNjOThcdWM3NGMgXHVjMjE4XHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjMjE4XHVjNWY0XHVjNzU4IFx1YzIxOFx1YjI5NCAxMDAsMDAwXHVjNzQ0IFx1YjExOFx1YzljMFx1YzU0YVx1YjI5NCBcdWM3NGNcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YzgxNVx1YzIxOFx1Yzc3NFx1YmE3MCwgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzE0Ylx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgUVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMGRkXHVkNzZjXHVhYzAwIFx1YzIxOFx1ZDU4OVx1ZDU1YyBcdWM1ZjBcdWMwYjBcdWM3NzQgXHVjYzI4XHViODQwXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gMCAmbGU7IFggJmxlOyAxMDAsIDEgJmxlOyBBICZsZTsgQiAmbGU7IFx1ZDYwNFx1YzdhYyBcdWMyMThcdWM1ZjRcdWM3NTggXHVkMDZjXHVhZTMwLCAxICZsZTsgQyAmbGU7IFx1ZDYwNFx1YzdhYyBcdWMyMThcdWM1ZjRcdWM3NTggXHVkMDZjXHVhZTMwKzE8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD40XHViYzg4IFx1YzVmMFx1YzBiMFx1Yzc3NCBcdWIwOThcdWM2MmNcdWI1NGMgXHViOWM4XHViMmU0IFx1ZDU2OVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1ZDU2OVx1Yzc3NCAzMlx1YmU0NFx1ZDJiOCBcdWM4MTVcdWMyMThcdWI5N2MgXHViMTE4XHVjNWI0XHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjg0NCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlVQSVQiLCJkZXNjcmlwdGlvbiI6IjxwPk1pcmtvIGdvdCB0aXJlZCBvZiBpbXBsZW1lbnRpbmcgYWxsIGtpbmRzIG9mIGRhdGEgc3RydWN0dXJlcyBmb3IgZGlmZmVyZW50IHRhc2tzLiBTbywgaGUgZGVjaWRlZCB0byBjb21lIHVwIHdpdGggdGhlIHVsdGltYXRlIHN0cnVjdHVyZSwgb25lIHRoYXQgd2lsbCBhbGxvdyBoaW0gdG8gbWFuaXB1bGF0ZSB3aXRoIGhpcyBmYXZvcml0ZSBudW1iZXIgc2VxdWVuY2UuIEhlbHAgaGltITxcL3A+XHJcblxyXG48cD5NaXJrbyB3aWxsIGdpdmUgeW91IGhpcyBudW1iZXIgc2VxdWVuY2UsIGFuZCBhIHNlcXVlbmNlIG9mIHF1ZXJpZXMgeW91IG11c3QgZXhlY3V0ZS4gRWFjaCBxdWVyeSBlaXRoZXIgYXNrcyBmb3IgaW5mb3JtYXRpb24sIG9yIG1vZGlmaWVzIHRoZSBleGlzdGluZyBzZXF1ZW5jZS4gUG9zc2libGUgcXVlcnkgdHlwZXMgYXJlIGxpc3RlZCBiZWxvdy48XC9wPlxyXG5cclxuPHRhYmxlIGNsYXNzPVwidGFibGUgdGFibGUtYm9yZGVyZWRcIj5cclxuXHQ8dGhlYWQ+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZCBzdHlsZT1cIndpZHRoOjEwJVwiPlF1ZXJ5IHR5cGU8XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwid2lkdGg6NDUlXCI+RGVzY3JpcHRpb248XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwid2lkdGg6NDUlXCI+RXhhbXBsZTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGhlYWQ+XHJcblx0PHRib2R5PlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+MSBBIEIgWDxcL3RkPlxyXG5cdFx0XHQ8dGQ+U2V0IGFsbCBlbGVtZW50cyBmcm9tIEF0aCB0byBCdGggKGluY2x1c2l2ZSkgdG8gdmFsdWUgWDxcL3RkPlxyXG5cdFx0XHQ8dGQ+KDksOCw3LDYsNSw0LDMsMiwxKSAmcmFycjsgMSAzIDUgMCZuYnNwOyZyYXJyOyAoOSw4LDxzdHJvbmc+MCwwLDAsPFwvc3Ryb25nPjQsMywyLDEpPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjIgQSBCIFg8XC90ZD5cclxuXHRcdFx0PHRkPkFkZCBYIHRvIEF0aCBlbGVtZW50LCAyKlggdG8gKEErMSl0aCwgJmhlbGxpcDssIGFuZCAoQi1BKzEpKlggdG8gdGhlIEJ0aCBlbGVtZW50PFwvdGQ+XHJcblx0XHRcdDx0ZD4oOSw4LDcsNiw1LDQsMywyLDEpICZyYXJyOyZuYnNwOzIgMyA1IDImbmJzcDsmcmFycjsgKDksOCw8c3Ryb25nPjksMTAsMTEsPFwvc3Ryb25nPjQsMywyLDEpPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjMgQyBYPFwvdGQ+XHJcblx0XHRcdDx0ZD5JbnNlcnQgbmV3IGVsZW1lbnQgd2l0aCB2YWx1ZSBYIGltbWVkaWF0ZWx5IGJlZm9yZSB0aGUgQ3RoIGVsZW1lbnQ8XC90ZD5cclxuXHRcdFx0PHRkPig5LDgsNyw2LDUsNCwzLDIsMSkmbmJzcDsmcmFycjsmbmJzcDszIDQgMTAwJm5ic3A7JnJhcnI7ICg5LDgsNyw8c3Ryb25nPjEwMCw8XC9zdHJvbmc+Niw1LDQsMywyLDEpPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjQgQSBCPFwvdGQ+XHJcblx0XHRcdDx0ZD5GaW5kIHRoZSBzdW0gb2YgYWxsIGVsZW1lbnRzIGZyb20gQXRoIHRvIEJ0aDxcL3RkPlxyXG5cdFx0XHQ8dGQ+KDIsMTgsNyw2LDEsNCw3LDcsMikmbmJzcDsmcmFycjsmbmJzcDs0IDYgNyZuYnNwOyZyYXJyOyByZXN1bHQ6IDExPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90Ym9keT5cclxuPFwvdGFibGU+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgaW50ZWdlcnMgTiBhbmQgUSAoMSAmbGU7IE4sIFEgJmxlOyAxMDAgMDAwKSwgdGhlIHN0YXJ0aW5nIHNlcXVlbmNlIGxlbmd0aCBhbmQgdGhlIG51bWJlciBvZiBxdWVyaWVzLjxcL3A+XHJcblxyXG48cD5UaGUgZm9sbG93aW5nIGxpbmUgY29udGFpbnMgdGhlIHN0YXJ0aW5nIHNlcXVlbmNlLiBTZXF1ZW5jZSBjb25zaXN0cyBvZiBub24tbmVnYXRpdmUgaW50ZWdlcnMgbm90IGdyZWF0ZXIgdGhhbiAxMDAwMDAgdGhhdCBhcmUgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlLjxcL3A+XHJcblxyXG48cD5UaGUgZm9sbG93aW5nIFEgbGluZXMgY29udGFpbiBxdWVyaWVzIGluIHRoZSBmb3JtYXQgZGVzY3JpYmVkIGFib3ZlLiBJbiBhbGwgcXVlcmllcywgMCAmbGU7IFggJmxlOyAxMDAsIDEgJmxlOyBBICZsZTsgQiAmbGU7IGN1cnJlbnRTZXF1ZW5jZUxlbmd0aCwgYW5kIDEgJmxlOyBDICZsZTsgY3VycmVudFNlcXVlbmNlTGVuZ3RoKzEuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggcXVlcnkgb2YgdHlwZSA0IG91dHB1dCBvbmUgbGluZSBjb250YWluaW5nIHRoZSByZXF1ZXN0ZWQgc3VtLjxcL3A+XHJcblxyXG48cD5Ob3RlOiBub3RpY2UgdGhhdCBzb21lIHN1bXMgd29uJnJzcXVvO3QgZml0IGludG8gMzItYml0IGludGVnZXIgZGF0YSB0eXBlLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Contest > Croatian Open Competition in Informatics > COCI 2010/2011 > Contest #7 6번