You understood it right that for certain mo-left and mo-right I have a segtree each of whose node stores number of distinct elements in its corresponding range [i,j]. Clearly finding kth largest element means kth largest element in range [1,N] (Remember all array elements are mapped to numbers 1 to N). This is a basic query. Now if I query giving k to the root node it will check if its left child has more than k elements. If yes it will go to the left child and repeat the procedure. If left child has less than k elements it will go the right child with parameter k-(count of left child) and then repeat the procedure. This process will continue until the leaf node is reached, hence taking O(height) = O(log n) time.
1 Like
Okay, thank you.
@grey_code Thanks a lot, that was great explanation, I understood if correctly once I read this followed by seeing your code for it.
Though I believe that the prev and next can be eliminated by using a frequency map for current range i.e. mo-left to mo right.
@grebnesieh Thanks a lot for sharing your solution. Understood a whole new way to use dynamic pointers. I solved it after reading the editorial in N* log^ 3( N) and still got AC:) but I still couldnāt get how to reduce memory consumption to log( N) using persistent segment tree. Your approach taught me both the log( N) memory as well as N* log^ 2( N) approach. Keep sharingā¦:D.
Hereās my solution( N* log^ 3( N) ): https://www.codechef.com/viewsolution/10294528
Iād love to get any reviews on my solution to improve the approach or any explanation on how did it pass the time limit.
1 Like
How do I go from where I currently am(4-6 questions in Long Challenges) to solving questions like these?