Range Query Update Problem.

Правка en1, от ajraj27, 2020-03-30 00:21:23

Shivansh wants to give chapo to Arpit, but only if he is able to solve the following problem. As you are a dear friend of Arpit, you decide to help Arpit solve the problem. Given an array Arr of N numbers. You have to process Q queries on that array. Queries can be of following types : (1)add x to index y (2) given y compute sum of (Arr[i]*(y%i)) for i from 1 to N.

Input First Line of input contains two space separated integers N and Q. Second Line contains N space separated integers Arr[1] Arr[2] ..... Arr[N] Next Q lines describe one query each and can be one of the two type:

-> 1 i X — Add X to index i. -> 2 Y — compute sum of (Arr[i]*(Y%i)) for i from 1 to N.

Constraints 1 <= N,Q <= 100000 1 <= Arr[i], X, Y <= 100000 1 <= i <= N

Output For each second type query output one integer per line — answer for this query.

Sample input 4 3 3 2 3 4 1 2 1 2 10 2 12

Sample output 11 0

I think it can be solved by segment tree, but I'm not able to figure out how to handle 'y' ?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en5 Английский ajraj27 2020-03-30 00:29:25 90 Tiny change: 'handle 'y' ? \n\n[user:errichto][user:tourist] ' -> 'handle 'y'?\n\n[user:tourist]'
en4 Английский ajraj27 2020-03-30 00:27:03 34 Tiny change: 'dle 'y' ? ' -> 'dle 'y' ? \n\n[user:errichto][user:tourist] '
en3 Английский ajraj27 2020-03-30 00:25:52 4
en2 Английский ajraj27 2020-03-30 00:25:19 24
en1 Английский ajraj27 2020-03-30 00:21:23 1070 Initial revision (published)