Maintaining a Sequence

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 3.0s
Memory limit: 256M

Author:
Problem type

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

Operation Input Format Description
1. 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.
2. Get Sum GET-SUM posi tot Starting at the posi-th number in the current sequence, output the sum of tot consecutive numbers.
3. 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
MAKE-SAME 3 3 2
GET-SUM 5 4
MAX-SUM
MAKE-SAME 2 1 12
MAX-SUM
GET-SUM 8 2

Sample Output

-1
10
0
9
21
9

Constraints

The data in the input is guaranteed to be valid, and will always refer to existing positions in the sequence.

In test data worth 40\% of the points, N \le 100.
In test data worth 100\% of the points, N \le 100\ 000.

In test data worth 100\% of the points, the value of any number in the sequence will be in the range [-10\ 000, 10\ 000].
In test data worth 100\% of the points, M \le 100\ 000.


Comments


  • 1
    mastery  commented on Nov. 30, 2018, 6:42 p.m.

    definitely not Holy Grail War


    • 0
      _  commented on June 16, 2019, 9:54 p.m.

      definitely not as cheesable as holy grail war