동적 수열 자료 구조

시간 제한1초메모리 제한128 MB

요약
구간 대입, 구간 등차수열 더하기, 중간 삽입, 구간 합 질의를 모두 효율적으로 처리하는 자료구조를 설계하는 문제입니다.
난이도

어려움10점 중 8점

유형
세그먼트 트리, 배열, 구현
정답자
아직 제출이 없습니다

문제

정수 수열에 다음 네 가지 연산을 차례대로 수행한다. 위치는 현재 수열을 기준으로 1번부터 센다.

형식설명
1 A B XA번째부터 B번째까지의 모든 수를 X로 바꾼다.
2 A B XA번째 수에는 X, A+1번째 수에는 2*X, ..., B번째 수에는 (B-A+1)*X를 더한다.
3 C XC번째 수 바로 앞에 X를 삽입한다. C가 현재 수열의 크기+1이면 맨 뒤에 삽입한다.
4 A BA번째 수부터 B번째 수까지의 합을 출력한다.

초기 수열과 수행할 연산들이 주어질 때, 4번 연산이 나올 때마다 그 결과를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 Q가 주어진다. N은 초기 수열의 크기이고, Q는 수행할 연산의 개수이다. (1 <= N, Q <= 100,000)

둘째 줄에는 초기 수열의 원소 N개가 공백으로 구분되어 주어진다. 각 원소는 100,000을 넘지 않는 음이 아닌 정수이다.

다음 Q개 줄에는 수행할 연산이 차례대로 주어진다. X가 있는 연산에서는 0 <= X <= 100이다. 구간 연산에서는 1 <= A <= B <= 현재 수열의 크기이고, 삽입 연산에서는 1 <= C <= 현재 수열의 크기+1이다.

출력

4번 연산이 주어질 때마다 해당 구간의 합을 한 줄에 하나씩 출력한다. 합은 32비트 정수 범위를 넘을 수 있다.

예제2

  1. 예제 1

    입력
    5 5
1 2 3 4 5
1 5 5 0
4 4 5
4 5 5
2 1 5 1
4 1 5
    예상 출력
    4
0
25

  2. 예제 2

    입력
    1 7
100
3 1 17
3 2 27
3 4 37
4 1 1
4 2 2
4 3 3
4 4 4
    예상 출력
    17
27
100
37