题目大意
您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作:
$1$. 插入$x$数
$2$. 删除$x$数(若有多个相同的数,因只删除一个)
$3$. 查询$x$数的排名(若有多个相同的数,因输出最小的排名)
$4$. 查询排名为$x$的数
$5$. 求$x$的前驱(前驱定义为小于$x$,且最大的数)
$6$. 求$x$的后继(后继定义为大于$x$,且最小的数)
在jiry_2大佬的研究下,线段树有了全新一类的应用,也使得线段树从NOIP难度上升了许多。无法使用懒标记的区间取最值问题与难以分析的历史最值问题成为了线段树全新的难点。
某些不基于旋转或虽旋转但具有一定特殊性质的平衡树可以优美地解决一些旋转类平衡树所难以解决的问题,这一类平衡树往往具有特殊的定义或性质。