# Algoflux Qualifiers

How to solve 5th problem ?

4 Likes

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 ).

3 Likes

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:

1. sum of all values which are greater than a index K , query(K)

2. 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

1. For each query j whose left endpoint is i , ans[j] = query(K)

2. update(S[A[i]] , i * S[A[i]])

3. 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``````
2 Likes

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.