A Combining Problem

View as PDF

Submit solution

All submissions

Best submissions

Points: 20

Time limit: 0.6s

Memory limit: 256M

Author:

Ninjaclasher

Problem type

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

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

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

Input Specification

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

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

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

Output Specification

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

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