Hey guys,
Can you explain your approach to solve PRMQ from june 17 long? I am aware BIT is being used in most solutions. I am not able to decipher how the thing works. Thanks!
Hey you can use Segment Tree/Merge sort tree along with Binary search ( to answer the query ).
1)Create a segment tree in which the Leaf node should contain all the factors of the array element repeated the number of times of its exponent in prime factorization of that number.This can be done by creating a Smallest Prime Factor array in the sieve function itself.
.Also You should first create such vectors for all the array elements and sort these factors as they may be arranged in un-ordered manner.Only then implement the building of tree.
The Tree should look like vector Tree[4*100005];
2)The merge logic should be such that it accumulates all the primes (repeated as well) in the Parent node
Example : - child 1 has 2,2,2,3,5,7 and child 2 has 2,3,3,3,7 then the parent of the children will be having 2,2,2,2,3,3,3,3,5,7,7.
3)In the query operation Do Binary search to obtain THE INDEX OF First element greater than equal to X and index of the last element having Value less than equal to Y. This can be done using upper_bound & lower_bound.
Finally you return answer = difference of these indices.
code Link For reference:-link text
Hope that helps
1 Like
I used some what a different approach, by creating individual segment trees in each index of the array , thus making N segment trees and then store the required prime factors in the leaf nodes of the trees and then answering each query in between two segment trees . However to construct N segment trees you need persistent technique otherwise it would take infeasible amount of memory and time .
Hey Can you please elaborate this approach I wanted to know how to implement this algorithm .I was unable to do so. Thanks in advance
Used Approach
- Pre-calculate primes up to 1000000 (standard sieve algorithm)
- Assign to each prime (from 1.) an index (just sequential)
- Assign an index to each number in 1-1000000 (for x - stores prime index >=x) - that is just for faster
lookup later - Create 6 Fenwick Trees that spans the whole array for primes 2,3,5,7,11,13 (that massively reduces other prime dividers) (reminder: Fenwick trees allow to get the sum of any range l-r as Sum[r]-Sum[l-1])
- Now for each X[i] : first remove any primes (2,3,5,7,11,13) with their powers and fit them (add powers at location i) in appropriate Fenwick tree (from 4.)
- Now run modified get_factors routine to calculate prime index (rather than actual prime factor) and its power (obviously if still X[i] > 1 after removing all small primes, removing first 6 primes leaves not more then 4 different factors possible)
- Populate dividers structure for each X[i] remembering number of factors and powers (to reuse later)
- Create one more Fenwick tree for all other prime factors (>13) initially empty
- Now use MO’s algorithm , sort queries by the left block index and then right boundaries.
When running MO’s algorithm:
-
When adding Xi: add all its dividers powers (>13) at dividers indices place into Fenwick tree (from 8.) (add + power)
-
When removing Xi: sub all its dividers powers at dividers indices place from Fenwick tree (add - power)
-
When querying: first get prime indices from actual boundaries [x-y] and query Fenwick tree [xi-yi]. Also add any of base primes (2,3,5,7,11,13) from range [l,r] if they are in [xi,yi] - that you can get from the 6 separate Fenwick trees (from points 4. & 5.)
That was sufficient to get the full score.
I hope that helps.
1 Like
Thanks @lboris Can you suggest some simpler problems solvable with MO’s algorithm? I feel this is a bit advanced for my level. I am accepting @vidit_123 solution as I am more familiar with segtrees. Thanks!
This is excellent. Thanks 
Mo’s algorithm is a generic idea that can be applied to many problems specially with multiple queries or where persistent implementation is required.
The following two links have very good explanation and appropriate use cases:
https://www.hackerearth.com/practice/notes/mos-algorithm/ and
https://blog.anudeep2011.com/mos-algorithm/
Great that it helped !!