Here is the Link for the problem for those who are just surfing the forum randomly ;) DIFFICULTY EasyMedium PREREQUISITE PROBLEM: EXPLANATION We are required to use LeastPrimeDivisor(x)[LPD] in both of our queries, so a preprocessing step can be to evaluate and store LPD of all the Ai's in an array, say Sieve[], Since Ai <= 10^6 if (you are new to sieve): If (you are new to RMQ and Segment tree): Topcoder Tutorial GET(L,R) query asks us to return the maximum of LPD of all Ai in range [L, R], equivalently its a RangeMax query which can be done using segment tree where each internal node of segment tree holds the maximum of LPD of its two children. So first build a segment tree which support rangemax query and return max(LPD) . Since we already have LPD for all element in sieve, this step isn't much of an issue. see code for more clarification.GET(L, R) takes O(logN) time per call as usual. UPDATE(L, R) As you can expect is our RangeUpdate query, seeing range updates we might be tempted to use lazy propagation at first, but thinking carefully, we can notice that lazy terms provides no useful information on how to update a node's for its maximum value of LPD. So we are better with point updates.But the problem with point updates is they take O(logn) per call, and calls in our worst case can be N for UPDATE(1, N)naively, doing point updation on this range would give O(NlogN) time per query or equivalently O(M*NlogN) = O(N^2logN) for M of such queries, which will certainly time out. OBSERVATION If you watch closely, each element in the range [L, R] of the array A is being reduced by a factor of its LPD, also after an element is reduced to 1 it remains 1 forever. the limit for an element in our case is 10^6 which is roughly 2^20, Thus we are assured that each of our element would become 1 after going through at max 20 updates(convince yourself). Thus we can stop updating those element which are already reduced to 1, so our worst case time complexity for M UPDATE(1, N) queries reduces to O(20*NlogN)(independent of M) ANALYSIS PreProcessing time in sieving : O(NloglogN) A similar question that you can try is GSS4 SPOJ this is a classical SPOJ problem and nearly everyone who has ever got to know about segment tree knows about it, so you can easily guess why there were so much of AC's for that problem. NOTE Actually in practice the update operation can be much faster than O(20*NlogN). if you implement UPDATE(L, R) operation by doing naive point update over the range(L, R) then surely its going to take O(NlogN) time per operation but if you implement UPDATE function like the one to BUILD the segment tree then each UPDATE(L, R) will take O(RL+1) time, if RL+1 dominates logN, otherwise it would be logN. Our worst case would be the same as all the query can be of type UPDATE(L, L)(here logN dominates RL+1 term) in which case the operation will take O(logN) time, same as naive point update, comment if you need more on this.In the analysis, to make thing worst for us i assumed all the queries are of GET type and we still account for all the possible UPDATE operations. asked 15 Sep '16, 15:15

@ashwanigautam I didn't use Seg Tree , still got an AC. Although, I used the idea that after certain(max. 20) number of updates any number would become 1 and stay 1 forever so it is useless to traverse that position in update or get operation. I used 2 extra arrays to store and jump to next number which is not 1. Here is the link to the AC solution. Nice editorial by the way. Cheers mate. answered 18 Sep '16, 01:19
2
yes mate it served the purpose, the memory and time which your code took were somewhat on higher side, you might want to squeeze them in future. Cheers
(18 Sep '16, 16:04)
@ashwanigautam Yes, you're right, my code wasn't very time efficient. I didn't know how to properly implement the SegTree back then. :D I learned it now though. Link to Segtree method btw, again, Thanks for the great editorial man. It helped a lot. (Y)
(18 Nov '16, 22:53)

In your code instead of Creating a node to check whether update is required or not, you can simply check if(tree[node] == 1), my solution : http://p.ip.fi/nySQ answered 15 Sep '16, 18:32
oh yes, thanks.. missed this, reduced the program memory to 8.4MB (Y)
(15 Sep '16, 18:34)
I also did the same thing @yougaindra , your solution is very similar to mine.
(18 Sep '16, 09:48)

The official editorial is quite great, do read that :)