HDU 3487 Play with Chain (Splay tree)区间切割和反转操作。

代码:https://vjudge.net/solution/5720453
题目:https://vjudge.net/contest/110258#problem/A

包括区间切割和反转操作。

对于Splay处理区间[l,r],将l-1转至根部,将r+1转至根的右孩子,这样根的右孩子的左子树便为[l,r],相当犀利啊,Splay的操作大多基于这样的旋转操作。

对于切割,便是旋转之后,把子树先取下,然后再转到要插入的位置,将子树接上。

反转操作,加个懒惰标记,表示子树是否要交换,

版权声明:本文为now_ing原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接和本声明。