A Combining Problem

View as PDF

Submit solution

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

Author:
Problem type

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

  • 1 i k Combine k consecutive elements beginning at index i (including the element at index i) into one element in the current array. "Combining" means summing the values of the k elements into one.
  • 2 i Uncombine the element at index i in the current array into its original elements in the original array. (i.e. the element at index i in the current array is transformed back into the elements in a that is included in element i)
  • 3 i k Output the sum of k consecutive elements beginning at index i (including the element at index i) in the current array.

(1 \le k, i \le 10^5). Let M be the number of elements in the current array. Subtract M from i until i is in the range [1, M]. Let L be the number of elements to the right of or at index i in the current array. Subtract L from k until k is in the range [1, L].

Input Specification

The first line will contain two integers, N, Q (1 \le N, Q \le 10^5).

The second line will contain N integers, the values of the original array (1 \le a_i \le 10^4).

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

Output Specification

For each type 3 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

Comments


  • 12
    Riolku  commented on March 6, 2019, 3:44 p.m. edit 2

    For operation of type 2, will the index i always be a previously combined index?

    If not, should we simply do nothing?

    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?


  • 8
    Plasmatic  commented on March 6, 2019, 3:33 a.m.

    solid question