Splay Tree Problem — Can it be solved using Order Statistic Tree?

Revision en1, by -synx-, 2017-11-02 07:43:30

http://www.spoj.com/problems/ADALIST/
The problem asks to efficiently perform insert/erase/index at kth position!
I know it can be solved using Splay Tree easily in O(nlg(n)).
My question however is can we use Order Statistic Tree (PBDS) to solve it too? (inserting might cause issues, I think)

Tags splay-trees, pbds, order-statistic-tree

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English -synx- 2017-11-02 07:43:30 411 Initial revision (published)