A Combining Problem

View as PDF

Submit solution

Points: 20
Time limit: 1.0s
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.
  • 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

There are no comments at the moment.