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.