上次我使用splay。。没有A掉这道题。。非常的不爽。。
这次使用treap。。总算亲自把它A了。。
题目就看上一个吧。。基本的平衡树。。。
据说如果随机数据的话。。
AVL和SBT差不多是1*logn
Splay是3～4*logn的。。
Treap是2～3*logn的。。
实际上这道题离散化一下。。然后用线段树也能A。。估计快很多。。
Code:
http://ideone.com/Fie69wNz