Informatica Online Judge

  사악한 admin [2393 / 0959]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 12   Total Tried : 11


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

[33th 최지원 gs15120]
Writer ID : [gs15120]

Background

드디어 gs15120은 세그트리를 배웠다. 이제 gs15120은 길이 n의 수열 a1,...,an에 다음의 쿼리들을 각각 lgn의 시간복잡도로 처리할 수 있다.

0 i v : ai에 v를 더한다.
1 i j: ai부터 aj까지 합을 출력한다.

하지만 사악한 admin은 늘 그렇듯 문제를 살짝 바꾸는 것으로 난이도를 올려버렸다. 이제 gs15120이 처리해야하는 쿼리들은 다음과 같다.

0 i j v: ai~aj에 v를 더한다.
1 i j: ai부터 aj까지 합을 출력한다.

gs15120은 라-이-트한 koistudy유저이기 때문에, 시간복잡도를 nq에서 더 줄이지 못한다. 8ㅅ8

여러분이 gs15120을 도와주자.

Input

첫줄에 수열의 길이 n과 쿼리의 개수 q가 차례로 주어진다.(1<=n,q<=100,000)
다음 q줄에 위가 같은 형식의 쿼리가 입력된다.(1<=i,j<=n, 1<=v<=10000000)

Output

각 쿼리의 출력값을 한줄씩 출력한다.

IO Example

입력
8 6
0 2 4 26
0 4 8 80
0 4 5 20
1 8 8
0 5 7 14
1 4 8

출력
80
508

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