题意:给定一个序列,要求可以插入、删除小于某个值的所有数、所有值同时加上x、查询当前第k大的数。

思路:

首先,我们感觉这是一道Splay的裸题,但是看到需要区间加减就懵了。
但是仔细一想不难发现,由于所有的加减操作是对全部数据而言的,所以我们可以建立一个变量保存全部的数相对于Splay中的值加减了多少。
至于第k大询问,我们可以给每个节点新建一个值:子树大小,以便进行二分。
与以往的Splay不同的是,我们的值可能重复,所以需要给每个节点新建一个值:值的个数。这样才可以既满足Splay的有序性,又可以方便递归。
所以我们的Splay节点的结构差不多就出来了: