HDU 1890 Robotic Sort (splay,区间翻转)

给n个数字,现在模拟一种排序,将第i个数字到第i大的数字翻转。每次翻转前输出第i大的数字在什么位置。

splay不用存任何key,只需要更具输入的数字建splay树(数字已经根据位置的大小变成一棵splay),于是每次翻转操作只需要将当前最小的数字splay到根那么根的左子树的大小+i就是当前第i大数字的位置,操作完记得将根删除。
翻转操作其实就讲当前子树左右子树翻转(相对大小改变了),注意往下打标记的先后,特别是在splay的时候需要将push_down在判断左右孩子。

 

LEAVE A COMMENT