아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

수열 관리

시간 제한2초메모리 제한256 MB

요약
수열을 유지하며 구간 삽입, 삭제, 구간 대입, 구간 뒤집기, 구간 합, 전체 최대 연속 부분합을 처리한다.
난이도

어려움10점 중 9점

유형
동적 계획법, 구현, 배열, 분할 정복
정답자
아직 제출이 없습니다

문제

다음 6가지 연산을 지원하면서 수열을 관리하는 프로그램을 작성하시오.

연산입력 형식설명
1. 삽입INSERT posi tot c1 c2 … ctot현재 수열의 posi번째 수 뒤에 c1, c2, …, ctot까지 총 tot개의 수를 삽입한다. 수열의 맨 앞에 삽입할 때는 posi가 0이다.
2. 삭제DELETE posi tot현재 수열의 posi번째 수부터 시작해서 연속한 tot개의 수를 삭제한다.
3. 변경MAKE-SAME posi tot c현재 수열의 posi번째 수부터 시작해서 연속한 tot개의 수의 값을 모두 c로 바꾼다.
4. 뒤집기REVERSE posi tot현재 수열의 posi번째 수부터 시작해서 연속한 tot개의 수의 순서를 뒤집는다.
5. 구간 합GET-SUM posi tot현재 수열의 posi번째 수부터 시작해서 연속한 tot개의 수의 합을 출력한다.
6. 최대 합MAX-SUM현재 수열에서 (비어 있지 않은) 연속한 부분 수열의 합 중 최댓값을 출력한다.

입력

첫째 줄에 두 정수 N과 M이 주어진다. N은 수열의 처음 길이이고, M은 연산의 개수이다.

둘째 줄에 처음 수열을 이루는 N개의 정수가 주어진다.

그다음 M개의 줄에 위에서 설명한 형식 중 하나로 명령이 주어진다.

출력

입력에 나오는 각 GET-SUM 또는 MAX-SUM 연산마다 그 결과를 한 줄에 하나씩 출력한다.

제한

  • 어느 시점에서든 수열에는 적어도 1개의 수가 들어 있다.
  • 입력 데이터는 올바르며, 항상 수열에 실제로 존재하는 위치를 가리킨다.
  • 어느 순간에든 수열에 들어 있을 수 있는 수의 개수는 최대 500 000개이다.
  • 수열에 들어 있는 각 수의 값은 [-1000, 1000] 범위에 있다.
  • M ≤ 20 000
  • 삽입되는 모든 값의 합은 4 000 000을 넘지 않는다.
  • 입력은 20MB를 넘지 않는다.

예제1

  1. 예제 1

    입력
    9 8
2 -6 3 5 1 -5 -3 6 3
GET-SUM 5 4
MAX-SUM
INSERT 8 3 -5 7 2
DELETE 12 1
MAKE-SAME 3 3 2
REVERSE 3 6
GET-SUM 5 4
MAX-SUM
    예상 출력
    -1
10
1
10