Maintaining a Sequence

View as PDF

Points: 40 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

Please write a program that maintains a sequence, supporting the following $$6$$ operations:

Operation Input Format Description
1. Insert INSERT posi tot $$c_1\ c_2\ \ldots\ c_{tot}$$ After the $$posi$$-th number in the current sequence, insert a total of $$tot$$ numbers: $$c_1,c_2,\ldots,c_{tot}$$. Insertion to the beginning of the sequence will have $$posi$$ equal to $$0$$.
2. Delete DELETE posi tot Starting at the $$posi$$-th number in the current sequence, delete a total of $$tot$$ consecutive numbers.
3. Modify MAKE-SAME posi tot c Starting at the $$posi$$-th number in the current sequence, change all the values of $$tot$$ consecutive numbers to $$c$$.
4. Reverse REVERSE posi tot Starting at the $$posi$$-th number in the current sequence, reverse the order of $$tot$$ consecutive numbers.
5. Get Sum GET-SUM posi tot Starting at the $$posi$$-th number in the current sequence, output the sum of $$tot$$ consecutive numbers.
6. Max Sum MAX-SUM Output the largest sum of any (non-empty) consecutive subsequence of the current sequence.

Input Specification

The first line of input contains two integers $$N$$ and $$M$$, where $$N$$ is the initial length of the sequence and $$M$$ is the number of operations.

The second line of input contains $$N$$ integers, describing the initial sequence.

For the next $$M$$ lines, each line will contain a command in one of the formats described above.

Output Specification

For each GET-SUM or MAX-SUM operation in the input, output the result of the query on a separate line.

Sample Input

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

Sample Output

-1
10
1
10

Constraints

You may assume that at any given time, the sequence will contain at least $$1$$ number.
The data in the input is guaranteed to be valid, and will always refer to existing positions in the sequence.

In test data worth $$50\%$$ of the points, the sequence may contain up to $$30\ 000$$ numbers at any given moment.
In test data worth $$100\%$$ of the points, the sequence may contain up to $$500\ 000$$ numbers at any given moment.

In test data worth $$100\%$$ of the points, the value of any number in the sequence will be in the range $$[−1\ 000,1\ 000]$$.
In test data worth $$100\%$$ of the points, $$M \le 20\ 000$$, the sum of all inserted values will not exceed $$4\ 000\ 000$$, and the input will not exceed 20MB.