How to solve 5th problem ?
This question has two parts:
Part1- Precomputing i * (sum of different prime factors of A[i]) for all i and store in another array (say arr[]). This is pretty basic and can be done using Sieve.
Part2- Using a data structure to answer queries of the form l,r,k.
For this maintain a segtree whose leaf nodes contain values of arr[i].
Now, sort the queries with respect to k in increasing order.
After answering a query moving to next query involves updating all leaf nodes to 0 whose A[i] value is less than equal to k of the new query, and then answering range query(l,r).
Total no. of updates is atmost n and queries q. So total complexity of part2 is O( nlogn + qlogn ).
Pre requisites : Sieve , offline query , FenwickTree or SegmentTree
The sum of prime factors can be precomputed using a sieve for numbers less than 10^7
Lets call that S[i]
We need a data structure which supports 2 operations:
-
sum of all values which are greater than a index K , query(K)
-
increment the value at a particular index , update(i , val)
The basic idea is to process the queries offline . That is we won’t be solving the queries as and when they come . We will iterate each index in the array and process each endpoint in that index .
Let ans[j] store the answer to the j^{th} query
When we are in the i^{th} index of the array
-
For each query j whose left endpoint is i , ans[j] = query(K)
-
update(S[A[i]] , i * S[A[i]])
-
For each query j whose right endpoint is i , ans[j] = query(K) - ans[j]
You can visualize it as something similar to prefix sums
My Solution :
[1]
Complexity : $O((N + Q)log R)$ , $R$ = maximum sum of prime factors , for $N = 10^7 , R = 9999991$
I made a really trivial mistake while implementing a Fenwick Tree , so I wasn't able to submit during contest . I was able to fix it only after the contest.
[1]: https://www.codechef.com/viewsolution/12677829
I have a doubt. According to the solution given by @grey_code we will have to check for updates on leaf nodes after each query. So how would we do that ? wouldnt it take O(n) time ?
sort w.r.t k in decreasing order? I think it should be increasing order and then for each A[i]<=k update A[i]=0; Am i right ?
Yes you are right, will edit my answer.
Thanks.Your approach is very simple.Marked your answer as accepted
Thanks for writing detailed solution +1
No, as we do not check for all n leaf nodes to update. We know that leaf nodes that have been previously updated to 0 will remain 0. Only update new nodes less than equal to k in a new query. We can have sorted order of leaf nodes in some other array, and update each leaf node at most once.