PRMQ Editorial(Unofficial) [Simplicity gauranteed]

@vijju123 sure, I’ll take a look!

Here segment tree contains a sorted vectors of prime numbers of the elements which falls in the range of L to R.
Let me make it clear by an example
Problem:
suppose my array is like 2 3 4 5 4
Here l=1 and r=3
Here x=2 and y=4
Solution:
Now this segment l=1 and r=3 will give a vector like 2 2 2 3
here 1st 2 is for A[1](1 based indexing)
here 2nd and 3rd 2 are because of A[3]
here 3 is because of A[2]
now we will do binary search on this received vector and find the difference in the index corresponding to x and y which will give 4 for this case.
Hope this clears some of your doubts :slight_smile:

1 Like

Thanks for the editorial, I was trying to keep the frequency too, but yours approach is simpler(just keeping whatever the prime factor be as many times).:slight_smile:

@vijju123, @d4dev please have a look at it. It won’t take much time.

Are you sure that the elements in the merged nodes are sorted?

1 Like

@vishesh_345 I have a test case for you but its gonna be very hard for you to debug it.
5
2 45 14 546 475
1
2 5 10 1000
My ac code is giving ans as 2 your code is giving ans as 0.
Actually the problem is that you are applying binary search on an unsorted vector.
Look here: XOqxDU - Online C++0x Compiler & Debugging Tool - Ideone.com

1 Like

Good that you got a AC ^^

@tonny in your approach you can optimize your prime factorization method. You are using an approach O(sqrt(N)/2). You can have a look at my solution.

https://www.codechef.com/viewsolution/14642454
Also it is good to keep the frequency of every prime factor but it is not needed actually. You see total no. of prime factors all numbers in array is with O(N) space complexity because total no. of prime factors cannot exceed 19 (even if all are same that is). So even if you keep primes as it is there is no problem.
Hope it helps :slight_smile: