시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
2.0 초 512 MB 8001 1917 (24%) 1466
문제
길이 N의 수열이 주어진다. 이 수열의 초기값은 $1, 2, 3, ..., N$이다. 그런데 이 수열의 변경이 빈번히 일어나고, 그런 도중에 어떤 연속된 부분의 합을 구하려 한다. 만약 $N$이 $5$인 경우를 생각하자. 초기에는 $1, 2, 3, 4, 5$ 가 된다. 이 상황에서 $3$번째 수를 $9$로 변경하고 $4$번째 수를 $10$으로 변경하면 $1, 2, 9, 10, 5$가 된다. 이 때, $2$번째부터 $5$번째까지 합을 구하라고 한다면 $26$을 출력하면 되는 것이다. 또, 이 상태에서 $1$번째 수를 $-5$로 변경하고, $3$번째 수를 $5$로 변경하면 $-5, 2, 5, 10, 5$가 된다. 그 다음, $1$번째부터 $3$번째까지 합을 구하라고 한다면 $2$가 된다. 이러한 질의를 해결하는 프로그램을 작성하시오.
입력
첫 번째 줄에 정수의 개수 $N$이 주어진다. $(1 ≤ N ≤ 100,000)$ 두 번째 줄에 질이의 개수 $Q$가 주어진다. $(1 ≤ Q ≤ 200,000)$ 세 번째 줄부터 $Q$개의 줄에 걸쳐 질의의 정보가 주어진다. 각 질의는 다음 형태로 이루어진다. - $0~~x~~y$ : $x$번째 수를 $y$로 변경한다. $(1 ≤ x ≤ N, -100,000 ≤ y ≤ 100,000)$ - $1~~x~~y$ : $x$번째 수부터 $y$번째 수까지의 합을 구한다. $(1 ≤ x ≤ y ≤ N)$
출력
질의 중 1로 시작하는 질의에 대해, 구한 합을 한 줄에 하나씩 출력한다.
힌트
#### 입력 예제 ``` 5 7 1 2 4 0 3 9 0 4 10 1 2 5 0 1 -5 0 3 5 1 1 3 ``` #### 출력 예제 ``` 9 26 2 ```