문제
정올이는 문제마다 데이터 구조를 구현하는데 지쳤다.
그래서 정올이는 궁극적인 구조를 생각해내기로 하였다.
그 중 하나는 정올이가 좋아하는 수열로 바꾸는 것이다.
하지만 혼자서 처리하기에는 쉬운 문제가 아니므로 여러분에게 도움을 청하였다. 정올이를 도와주자.
정올이는 여러분에게 하나의 행에 수열을 제시할 것이다. 그리고 다음 행부터 여러분이 수행할 질의를 제시할 것이다.
각 질의는 합을 구하거나 수열의 일정구간의 값을 바꾸는 것이다. 가능한 질의 타입은 아래와 같다.
입력
첫 행에 수열의 길이를 나타내는 N과 질의의 수를 나타내는Q 가 공백으로 구분하여 입력된다. (1≤N, Q≤100,000)
다음 행에 공백으로 구분하여 수열이 입력된다.
수열의 수들은 100,000 이하의 음이 아닌 정수이다.
다음 Q 개의 행에 위의 표에서 제시한 질의 타입이 입력된다.
각 변수의 범위는 아래와 같다.
1 ≤ X ≤ 100 1 ≤ A ≤ B ≤ 주어진 수열의 길이
1 ≤ C ≤주어진 수열의 길이+1
출력
4번 질의에 대하여는 주어진 질의에 따른 결과를 한행에 하나의 수로 출력한다.
* 주의: 합은 32bit 정수범위를 초과할 수 있다.
예제1
입력
55
12345
1550
445
455
2151
415
출력
4
0
25
예제2
입력
17
100
3117
3227
3437
411
422
433
444
출력
17
27
100
37
출처
COCI 2010_2011 CONTEST #7