Informatica Online Judge

  구간 합/갱신 놀이 [1075 / 0433]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 263   Total Tried : 1761


The Champion of this Problem (C++) : gs16048 - ms / 474byte
My Best Submission (C++) : N/A

[JeongHJ 2014]

Background

n명의 학생들은 각자 자신만의 수를 하나씩 가지고 일렬로 서 있다.

오늘 게임은 n명의 학생들 중에서 a번째부터 b번째 학생들이 가진 수의 합을 구하는 것이다.

이 게임이 매우 쉬웠던지 지학, 한필이가 너무 쉽게 문제를 해결하고 놀고 있는 것이 못마땅하였다.

이에 기존에 일렬도 서 있는 학생들 중에서 원하는 학생이 가진 수를 바꾸는 규칙을 추가했다.

즉, 게임에서 주어진 규칙이 1이면 a, b 구간의 합을 출력하고, 2이면 p번째 학생이 가진 수를 q로 변경하는 것이다.

예를 들어, 3 5 2 1 4 3 의 각 수를 가지고 있는 6명의 학생이 일렬로 서 있고, 규칙 1 2 4 가 주어지면 2번째 학생부터 4번째 학생까지 3명의 학생이 가진 수의 합인 8을 출력한다.

만약 2 3 10 이 주어지면 3번째 학생이 가진 수를 10 으로 변경한다.

게임이 m번 진행되는 동안 각 게임에서의 결과를 출력하는 프로그램을 작성하시오.

Input

첫째 줄에 n과 m이 입력된다.
둘째 줄에 n개의 정수가 공백으로 분리되어 입력된다.
셋째 줄부터 m개의 게임이 입력되는데, 시작 수 a와 마지막 수 b가 입력된다.

그리고 입력되는 각 값의 범위는 -1000 ~ 1000 이며, 1 <= a <= b <= n을 만족한다.

[Sub-task Info]
- 20%의 데이터에 대해서는 n, m <= 100 을 만족한다.
- 20%의 데이터에 대해서는 n, m <= 1,000 을 만족한다.
- 20%의 데이터에 대해서는 n, m <= 10,000 을 만족한다.
- 20%의 데이터에 대해서는 n, m <= 100,000 을 만족한다.
- 20%의 데이터에 대해선는 n <= 1,000,000 ; m <= 100,000 을 만족한다.

Output

게임의 진행 순서대로 결과를 한 줄에 하나씩 출력한다.

IO Example

입력
6 4
3 5 2 1 4 3
1 2 4
1 1 1
2 3 10
1 3 6

출력
8
3
18

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]