I've used disjoint-set data structure with Fenwick's tree(to find k-th element in log^2(n)). But it taken TL.
And what about your solution? 

• a segment tree will provide a O(logn) running time per operation (147) frkstyc 2006-08-27 18:07:47
  • Re:a segment tree will provide a O(logn) running time per operation (182) 8031987 2006-08-27 18:29:08
    • binary search tree is another option (188) frkstyc 2006-08-27 18:31:35