## A Combining Problem

View as PDF

Points: 20
Time limit: 0.6s
Memory limit: 256M

Author:
Problem type

Given an array of integers, and queries, support the following operations:

• 1 i k Combine consecutive elements beginning at index (including the element at index ) into one element in the current array. "Combining" means summing the values of the elements into one.
• 2 i Uncombine the element at index in the current array into its original elements in the original array. (i.e. the element at index in the current array is transformed back into the elements in that is included in element )
• 3 i k Output the sum of consecutive elements beginning at index (including the element at index ) in the current array. . Let be the number of elements in the current array. Subtract from until is in the range . Let be the number of elements to the right of or at index in the current array. Subtract from until is in the range .

#### Input Specification

The first line will contain two integers,  .

The second line will contain integers, the values of the original array .

The next lines will each contain a valid query as defined above.

#### Output Specification

For each type query, output the answer on its own line.

#### Sample Input

3 9
1 3 4
1 1 2
3 1 1
3 1 2
2 1
3 2 2
3 2 1
1 2 2
1 1 2
3 10000 100000

#### Sample Output

4
8
7
3
8

Also, if we have an element that has been combined twice, what should we do? For example, given 1 2 3 4, then combining to 3 7 and further to 10, when uncombining, do we get 1 2 3 4 or 3 7?