COCI 2010_2011 CONTEST #7- 질의(UPIT) > 문제은행 : 정보올림피아드&알고리즘




2446 : 질의(UPIT)

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

문제

정묵이는 문제마다 데이터 구조를 구현하는데 지쳤다. 

그래서 정묵이는 궁극적인 구조를 생각해내기로 하였다. 

그 중 하나는 정묵이가 좋아하는 수열로 바꾸는 것이다. 

하지만 혼자서 처리하기에는 쉬운 문제가 아니므로 여러분에게 도움을 청하였다. 정묵이를 도와주자.

 

정묵이는 여러분에게 하나의 행에 수열을 제시할 것이다. 그리고 다음 행부터 여러분이 수행할 질의를 제시할 것이다. 

각 질의는 합을 구하거나 수열의 일정구간의 값을 바꾸는 것이다. 가능한 질의 타입은 아래와 같다.

 

 

 


입력형식

첫 행에 수열의 길이를 나타내는 N과 질의의 수를 나타내는Q 가 공백으로 구분하여 입력된다. (1≤N, Q≤100,000) 다음 행에 공백으로 구분하여 수열이 입력된다. 수열의 수들은 100,000 이하의 음이 아닌 정수이다. 다음 Q 개의 행에 위의 표에서 제시한 질의 타입이 입력된다. 각 변수의 범위는 아래와 같다. 1 ≤ X ≤ 100 1 ≤ A ≤ B ≤ 주어진 수열의 길이 1 ≤ C ≤주어진 수열의 길이+1

출력형식

4번 질의에 대하여는 주어진 질의에 따른 결과를 한행에 하나의 수로 출력한다. * 주의: 합은 32bit 정수범위를 초과할 수 있다.

입력 예

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

출력 예

4
0
25

입력 예

1 7
100
3 1 17
3 2 27
3 4 37
4 1 1
4 2 2
4 3 3
4 4 4

출력 예

17
27
100
37


경기도 안양시 동안구 평촌대로 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