Hey all, This problem can be solved using just segment tree, I have written a blog which explains my solution, you can visit it Here.
You can also use STL to shorten your code. My code using same approach
Hey thanks for the explanantion but could anyone please give the approach for this problem using square root decomposition? I don’t karma points to ask one, so am posting it here. I have tried using square root decomposition to solve this problem and am doing it in O(q*sqrt(n)*log(sqrt(n)) ) but am getting TLE for all cases in the last subtask. Here is my solution https://www.codechef.com/viewsolution/14214707. Any help would be welcome. Thanks!
Thank u for the link @hulk_baba
I want some segment tree problems with different senarious like June contest it gave 4 variable related PRIMEQ problem I know it is segment tree problem But I actually not understood what to put in the node…Help me…
@divyansh_gaba7 could you please explain your code
I’ve tried using BIT and MO’s but got two tles in last subtask nice solution @hulk_baba
can somebody plz post links to questions similiar like this?
where we have to made our own custom segment trees.
@yash_22 thank you.
You can refer it here
This problem has a pretty neat and straightforward solution if u process the queries offline. Observe that
F(L,R,X,Y) = F(1,R,X,Y) - F(1,L-1,X,Y)
So, first, we input all the queries together. Then we divide each query into 2 queries of type F(1,S,X,Y) and then sort these queries on S. After that, its simple point update range query which can be easily done with a BIT(or segment tree).
You can refer my solution here
Thanks a lot man! I still have a doubt. Shouldn’t 78500*250 give MLE for static arrays? I assumed that i would get an MLE and broke the problem into primes less than 1000 and greater than 1000 to overcome the issue.
Btw just created the array for all primes in a block and am getting AC. Wish I had tried this during the contest. Thanks again man! Here’s my solution https://www.codechef.com/viewsolution/14243563
PS: I really want to upvote your answer but don’t have enough reputation points to even upvote it.
- Basic Idea
- In a sorted array for X and Y we can use binary search to find the size of the interval is result with prime factors in the range of X and Y.
- Ex we have sorted array of prime factors (0 base array)2,2,5,5,5,11,11,23. Now query is for X=3,Y=14. Then index will be found using upper_bound and lower_bound. upper_bound-1 for right hand of the interval with search for Y , similarly lower_bound for the left hand of the interval with search for X.
- For above upperbound-1 = 6 , lowerbound = 2. Interval Size = 5.
- We will be using above basic idea and segment tree
- Our Leaf Node will be containing the prime factorization of the number in a sorted manner.
- For the process of merging two nodes here they are basically two sorted array we will use the idea of merging two sorted array from the MergeSort.
- Then the result will be calculated in the similar manner using binary search for the interval size as shown in basic idea and segment tree.
- My Submission Uncomment the cout statements for better understanding
- Codeforces Blog for Segment tree Implementation
I have a question, I don’t know why but for me, just for computing the prime factors for each of the numbers took 0.4 seconds, as seen in here,link, can anyone tell me what I was doing wrong here? I am not even doing anything for the queries, the time for computing the primes itself is 0.4 seconds.