P2042 [NOI2005] Sequence Maintenance

Please write a program to maintain a sequence that supports the following $6$ operations: | ID | Name | Format | Note | | :-----------: | :-----------: | :-----------: | :----------- | | 1 | Insert | $\operatorname{INSERT}\ posi \ tot \ c_1 \ c_2 \cdots c_{tot}$ | Insert $tot$ numbers $c_1, c_2 \cdots c_{tot}$ after the $posi$-th number of the current sequence; if inserting at the beginning of the sequence, then $posi$ is $0$. | | 2 | Delete | $\operatorname{DELETE} \ posi \ tot$ | Starting from the $posi$-th number of the current sequence, delete $tot$ consecutive numbers. | | 3 | Make-Same | $\operatorname{MAKE-SAME} \ posi \ tot \ c$ | Starting from the $posi$-th number of the current sequence, set $tot$ consecutive numbers all to $c$. | | 4 | Reverse | $\operatorname{REVERSE} \ posi \ tot$ | Take the $tot$ numbers starting from the $posi$-th number, reverse them, and put them back in the original position. | | 5 | Get-Sum | $\operatorname{GET-SUM} \ posi \ tot$ | Compute and output the sum of the $tot$ numbers starting from the $posi$-th number of the current sequence. | | 6 | Max-Subarray Sum | $\operatorname{MAX-SUM}$ | Find a contiguous subarray of the current sequence with the maximum sum and output that maximum sum. |

The first line contains two integers $N$ and $M$, where $N$ is the number of elements in the initial sequence, and $M$ is the number of operations to perform. The second line contains $N$ numbers describing the initial sequence. Each of the following $M$ lines contains one command; see the table in the Description for the formats.

For each $\operatorname{GET-SUM}$ and $\operatorname{MAX-SUM}$ operation in the input, print the result to the output in order, one answer (number) per line.

#### Constraints - You may assume that at any time, the sequence contains at least $1$ number. - The input is guaranteed to be valid, i.e., the specified positions always exist in the sequence. - For $50\%$ of the testdata, the sequence contains at most $3 \times 10^4$ numbers at any time. - For $100\%$ of the testdata, the sequence contains at most $5 \times 10^5$ numbers at any time; each number is within $[-10^3, 10^3]$ at any time; $1 \le M \le 2 \times 10^4$; the total count of inserted numbers does not exceed $4 \times 10^6$. Problem statement provided by @syksykCCC. Translated by ChatGPT 5