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 :
add x to index y
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
It’s from a coding challenge which has ended now.
Link - https://my.newtonschool.co/course/ldrj7tqzlt/timeline/
@everule1 @aryan12 @anon55659401 @waqar_ahmad224 @tmwilliamlin @ajaymalik
This problem can be solved by using Segment tree,try it own your own first.You will definitly be able to solve.
Yeah I know it is of segment tree, but how to deal with ‘y’ ?
Anyone please update on this?
This is tricky (speaking as an orange on CF). To solve this, you have to kind of tear down the concept of modulo.
First, using a basic segment tree, query the sum of the whole array and multiply it by Y. Then, instead of directly computing the mod for each index, we figure out how much modding by each index will decrease our answer. For each index i, we decrease the answer by A_i \cdot i \cdot \lfloor \frac{Y}{i} \rfloor.
Let’s focus on \lfloor \frac{Y}{i} \rfloor. I claim that for any Y, there are at most O(\sqrt{Y}) distinct values of \lfloor \frac{Y}{i} \rfloor. Why? For all i > \sqrt{Y}, \lfloor \frac{Y}{i} \rfloor < \lfloor \frac{Y}{\sqrt{Y}} \rfloor = \sqrt{Y}. And for all i \leq \sqrt{Y}, there is no bound, but there are only \sqrt{Y} valid i \leq \sqrt{Y}. So there are at most 2\sqrt{Y} possible values of \lfloor \frac{Y}{i} \rfloor.
Now let’s group ranges of indices that have the same value of \lfloor \frac{Y}{i} \rfloor (by the proof above, there are at most 2\sqrt{Y} ranges). You can use this problem and its editorial for some insight of how to find these ranges, it’s mostly simple. For each value of \lfloor \frac{Y}{i} \rfloor, which I’ll call m for a specific range, we want to decrease the sum of A_i \cdot i \cdot m for that range. This can be done efficiently by using another segment tree that stores the sums of A_i \cdot i, rather than just A_i.
Complexity:
Update - O(\log(n)) (just two segment tree changes)
Query - O(\sqrt{Y}\log(n))
Query costs too much, while update costs too little. Maybe there’s a way to get this to O(Q\sqrt{Y}).
edit: you don’t need a segment tree for the global sum, but this optimization doesn’t really help much
1 Like
I claim that for any YYY, there are at most O(Y)O(\sqrt{Y})O(Y
) distinct values of ⌊Yi⌋\lfloor \frac{Y}{i} \rfloor⌊iY⌋.
I didn’t get this as an example take y=25 so according to you there are atmost 5 value of y/i,but there are 9 values. please help
I see the problem you mention in the link but unable to get the idea why we iterate only root(n) values(not understand the maths proof given in the editorial).
can u explain how 2 root(y) values
Let’s assume worst case, all values of \lfloor Y/i \rfloor from 1 to \sqrt{Y} are different. So after this all values will be less than \sqrt{Y}, which is another \sqrt{Y} values. So there are at most 2\sqrt{Y} values
My main doubt is how there are atmost root(y) values of floor(y/i).
That’s exactly what I answered.
Thanks, can u proof it mathematically.
Please.