We can do this question using sqrt decomposition also.Divide the array into sqrt n blocks and for each block maintain an array of sqrt n size in which ith element contains information required about the product of the elements in this block due to r=i.For r>=sqrt n just calculate the answer manually(it takes O(root n))and for r< sqrt n traverse the blocks to get the information.We can update in sqrt n time by checking divisors of that particular index and update in its block. So total complexity is O(n*root n).
If N=50,say. and we update the 12th element. Then we have to change the value of product for r=1,2,3,4,6,12. How will we do that? Do we have to iterate through each value of r?
I did this problem without using sqrt-decomposition…I made an array which stores the new value of friendliness at pth index during update query…I never updated the array which stores enjoyment for different values of R. During query 2, I checked whether there is an any update of friendliness int the multiples of r. In this way i updated my Answer…
See my solution here for more clarity… CodeChef: Practical coding for everyone
Another much easier method is to pre-compute answer for 1<= R<= min( N, 300). For R> 300 compute by iterating over 0 to N- 1, which takes O( N/ 300) since we make a jump of >300 during iteration. To update just alter the pre-computed values which takes O( min( 300, N)). So overall complexity becomes O( Q*N/300).
Can anyone explain me the setter’s code:
for (int i=1; i<=min(pos-1, sq); i++){
if ((pos-1)%i==0){
dig[i]-=log10(a[pos]+0.0);
dig[i]+=log10(val+0.0);
remain[i]=inv;
remain[i]%=inf;
remain[i]=val;
remain[i]%=inf;
Should’nt this be just min(pos,sq) as the setter had done 1 based indexing in his code?
you are decomposing a number r into two products r = a * b. Where a <= b. Hence you need to search until square root of r only to find a and b. Hence, the name square root decomposition.