题意：
给你一个初始为空的序列,让你支持以下操作
1.插入+x,-x到位置p,其中x是序列中没出现过的最小正整数,其中插入后+x在位置p,-x的位置是左边负数的个数和+x左边正数的个数一样且最靠右的位置
2.删除+x,-x 保证+x,-x在序列中存在
3.询问+x,-x之间的数之和
题解:
这题是做的几个splay题目里面比较烦的一个,所以写个博客记录下
首先插入操作是最烦的,求序列中没出现过的最小正整数用一个优先队列维护下就行,对于+x,我们先Get_kth(root,p)找到第p个数是那个数,然后把这个数splay到根然后把+x插到根的前面去,对于-x,由于我们要知道+x前面有几个正数,这里我是用了cnt[x][0]和cnt[x][1]来维护正数和负数在x的子树中的个数,这样我们就可以像计算siz一样计算正数与负数的个数,设+x前面有num个正数,我们就把第num+1个负数splay到根然后把-x插到根前面去,就满足了最靠右的要求,这里插入查找时注意没有这么多数的情况需要特判下
然后是删除操作,这个我们只要在插入的时候用一个数组维护下数x的下标是哪个,把下标对应的节点转到根删了就行
然后输求和操作,这和splay经典的区间操作一样把l-1splay到根,把r+1splay到根的右儿子,这样根的右儿子的左儿子就是我们需要操作的区间[l,r],在一般题目中我们需要新建两个节点来防止越界,这题就不需要了
#include
#include
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！
