### National Olympiad in Informatics, China, 2005

## Day 1, Problem 2 - Maintaining a Sequence

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

Operation | Input Format | Description |
---|---|---|

1. Insert | `INSERT ` | After the posi-th number in the current sequence, insert a total of tot numbers: c, _{1}c, …, _{2}c. Insertion to the beginning of the sequence will have _{tot}posi equal to 0. |

2. Delete | `DELETE ` | Starting at the posi-th number in the current sequence, delete a total of tot consecutive numbers. |

3. Modify | `MAKE-SAME ` | Starting at the posi-th number in the current sequence, change all the values of tot consecutive numbers to c. |

4. Reverse | `REVERSE ` | Starting at the posi-th number in the current sequence, reverse the order of tot consecutive numbers. |

5. Get Sum | `GET-SUM ` | 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 Format

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 Format

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

### Explanation

Initially, we have the sequence:

2 -6 3 5 1 -5 -3 6 3

For the operation GET-SUM 5 4, we must find the sum of the 4 consecutive elements starting at the 5th position, as highlighted in gray below. The answer is 1 + (-5) + (-3) + 6 = -1.

2 -6 3 5 1 -5 -3 6 3

For the operation MAX-SUM, we must find the largest sum of any consecutive subsequence, as shown below. The answer is 3 + 5 + 1 + (-5) + (-3) + 6 + 3 = 10.

2 -6 3 5 1 -5 -3 6 3

For the operation INSERT 8 3 -5 7 2, we insert the numbers -5 7 2 after the 8th number in the current sequence. The inserted numbers are highlighted in gray below.

2 -6 3 5 1 -5 -3 6 -5 7 2 3

The operation DELETE 12 1 indicates that the 12th number in the sequence must be deleted. In this case, it is the last number.

2 -6 3 5 1 -5 -3 6 -5 7 2

For the operation MAKE-SAME 3 3 2, the 3 consecutive numbers starting at the 3rd position are all changed to 2, as depicted below.

2 -6 3 5 1 -5 -3 6 -5 7 2

becomes:

2 -6 2 2 2 -5 -3 6 -5 7 2

For the operation REVERSE 3 6, we first extract the 6 consecutive elements starting with the 3rd number in the sequence:

2 -6 2 2 2 -5 -3 6 -5 7 2

Then, the extracted sequence 2 2 2 -5 -3 6, after being reversed to 6 -3 -5 2 2 2, is reinserted back into the original place:

2 -6 6 -3 -5 2 2 2 -5 7 2

For the final operations GET-SUM 5 4 and MAX-SUM, it shouldn't be hard to get the answers 1 and 10.

|← GET-SUM 5 4 →| 2 -6 6 -3 -5 2 2 2 -5 7 2 |← MAX-SUM →|

### Scoring

For each test case, your score will be determined as follows:

- If your program prints the correct answers to all GET-SUM operations at the correct locations in the output, then you will score 60% of points.
- If your program prints the correct answers to all MAX-SUM operations at the correct locations in the output, then you will score 40% of points.
- If your program correctly answers both types operations, then you will score 100% of points.

Please note: If your program can only correctly process one type of operation, then ensure that operations of the other type each receive a corresponding line. Otherwise, we cannot guarantee that your score will be accurate.

### 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 [-1000, 1000].

In test data worth 100% of the points, `M` ≤ 20 000, the sum of all inserted values will not exceed 4 000 000, and the input will not exceed 20MB.

All Submissions

Best Solutions

**Point Value:** 40 (partial)

**Time Limit:** 2.00s

**Memory Limit:** 256M

**Added:** Jun 02, 2014

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

kobortoron Aug 20, 2016 - 3:37:12 am UTC Caution