Okay glad that you were able to digest it now.
I have some doubts,please help me out clearing them.
1.How using only path compression as in tester’s solution has time complexity of O(logn) as observed through discussions above.
2.What is (alpha) in Q.
3.According to me time complexity should be O(Q) as in worst case we can perform q updates on consecutive elements and answering range queries.
@l_returns Can you explain in your solution how do you account for the fact that root having lower rank is made child of root having higher rank in union by rank method.In this method time complexity should be O(logn) as it form balanced trees but if we use only path compression then how time complexity is O(logn) as in tester’s solution.
This is also solvable using a balanced BST [set] where we insert a pair of elements which represents the range of active elements [\ne 0]. Initially the set it will have only 1 pair : [1, n] and when we delete an element we find the pair on which it lies and delete it. After deletion, insert two more pairs. Like for deletion x, find [l, r] l \le x \le r and then delete this pair. Insert two other pairs : [l, x-1] and [x+1, r]
Total operations are no more than 3.Q. Complexity is O(logQ * Q)
Using path compression complexity is O(Qalpha(Q)) for processing all queries
where alpha is a function which return a number less than 4Q in CP constraints so yeah linear complexity for path compression
Hey you can’t call it constant.
It’s O(Q*alpha(Q)).
You are saying like complexity of BS on q queries is O(q*\log_2(n)) and here n=10^5 and hence \log_2(n)=17
And time complexity is O(q*17).
Which means time complexity of is O(q) 
Though for our convince we can think as if it’s equivalent to O(Q) as alpha(Q)<=4 for all practical values of Q.
2 Likes
IDK proof of it. But you can Google about it. “Time complexity of Disjoint set union using path compression” or something similar to it. You will surely find some explaination on why is it’s O(Q*alpha(Q)) which people often refer as ~ O(Q*\log_2(Q))
1 Like
https://www.codechef.com/viewsolution/25036895
I am getting 80 points. My solution is working for original constraints but surprisingly not working for smaller subtasks. can anybody check my solution?
I know its Q*alpha(Q) by mistake I left one character.I have edited it now and I had written linear at the last before also. IDK what the confusion is about
Lazy Propagation would help if there would have been range updates. However, here we are only updating 1 index.
I have maintained a map which contains the zeroed out elements. How can we apply binary search in the range to get the max element. ??