CSP-S复习计划-Splay

写一种数据结构,来维护一些数,其中需要提供以下操作:

  1. 插入x数
  2. 删除x数(若有多个相同的数,应只删除一个)
  3. 查询x数的排名(若有多个相同的数,应输出最小的排名)
  4. 查询排名为x的数
  5. 求x的前驱(前驱定义为小于x,且最大的数)
  6. 求x的后继(后继定义为大于x,且最小的数)

这就是伸展树的基本操作,也是伸展树名字的由来(这里讲算法不讲历史)。
重要的的函数有RotateSplayDel其他的都是一些树上操作罢了。
代码如下:

 ......  查看更多

[HNOI2002]营业额统计

[HNOI2002]营业额统计
这题,其实就是伸展树裸题嘛。
就是找前驱后继,我们主要还是维护一颗伸展树,然后慢慢慢慢插点,然后找前驱后继就好了。
但是这里的前驱后继是可以相等的,所以我们要找x+1的前驱,x-1的后继,然后就好了呀。
留个坑用set其实好像也可以做,真的我很想试试但是懒。 ......  查看更多