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.

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!

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…

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.

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.****Solution**- 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.