Informatica Online Judge

  4개의 쿼리 [2406 / 0966]

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


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

[36th 김기현]
Writer ID : [gs18012]

Background

이 문제는 4종류의 쿼리가 있는 흔한 수열과 쿼리 문제이다. 한번 풀어보자.
쿼리는 다음과 같다.

1 a b X : a번째부터 b번째 수를 모두 X로 바꾼다.
수열(1,5,2,4,3) + 쿼리(1,2,4,6) -> 수열(1,6,6,6,3)

2 a b X : a번째 수에는 X를, a+1번째 수에는 2*X를, ... , b번째 수에는 (b-a+1)*X를 더한다.
수열(4,5,6,7,8,9) + 쿼리(2,3,6,1) -> 수열(4,5,7,9,11,13)

3 c X : 숫자 X가 수열의 c번째 원소가 되도록 숫자를 삽입한다.
수열(4,3,2,1) + 쿼리(3,2,7) -> 수열(4,7,3,2,1)

4 a b : a번째 수부터 b번째 수까지 모든 수를 더한 값을 출력한다.
수열(2,4,5,6) + 쿼리(4,1,3) -> 11 출력

Input

첫째 줄에 초기 수열의 길이를 나타내는 자연수 N과 쿼리의 수를 나타내는 자연수 Q가 공백으로 구분되어 입력된다.

둘째 줄에는 자연수 N개가 공백으로 구분되어 입력된다. 입력되는 자연수들은 초기 수열을 의미한다.

셋째 줄부터 Q개의 줄에는 쿼리가 들어온다.

입력값은 다음 조건을 만족한다.
1<=N<=100,000
1<=Q<=100,000
0<=(초기 수열의 항)<=100,000
1<=X<=100
1<=a<=b<=(현재 수열의 길이)
1<=c<=(현재 수열의 길이)+1

4번 쿼리가 반드시 하나 이상 존재함이 보장된다.

Output

4번 쿼리에 대하여 한 줄에 하나씩 결과를 출력한다. 답이 32비트 정수 범위를 넘어갈 수 있다.

IO Example

입력
4 5
1 2 3 4
1 1 3 1
4 2 3
2 3 4 3
3 2 9
4 1 5

출력
2
25

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