看了一个帖子，想了一种水过普通平衡树的方法，不知道对不对。

离线，把出现过的所有数值排序、离散化，记录每个数值的总排名，建立链表，插入、删除、查询前驱后继直接在链表进行，同时用树状数组维护各个数值出险次数的前缀和，查询排名从树状数组查询，查询第 $k$ 小用 二分+查询排名。

查询第 $k$ 小是 $\mathcal O(\log^2n)$，其他操作都是 $\mathcal O(\log n)$。