bzoj 3065: 带插入区间K小值 树套树

题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=3065


替罪羊树套权值线段树,照着hzwer写的…我说一说自己的理解吧

替罪羊树的每个点维护的信息是整颗子树所包含的那个区间,然后每个点有一颗权值线段树,储存它们所维护的那个区间里的权值分布情况,防止MLE,我们对权值线段树进行动态开点以及内存回收,在build替罪羊树时,是暴力进行插入每个点的操作的,复杂度有点高但不会爆炸,应该是O(nlogn^3)的吧..

插入操作:和正常的替罪羊插入时没有什么区别,只不过在经过每一个点的时候,需要进行一次给当前节点线段树的插入,由于题目说的是在第k个前插入一个数,所以我们将k–,这样方便进行计算

修改操作:就是相当于先插入新的值,再找到第x个数是什么,然后进行删除,可以一次递归完成,每次在经过这个点时,进行插入,然后判断左子树线段树中的点数+1(就是左子树大小+1)与x的关系,如果相等就可以记录一下后进行修改与返回,我们可以将返回值设为我们要删除的值,这样上面的层就可以简单地知道我们要删除哪个

查询操作:我们需要找到要进行查询的所有的区间,所以用两个数组记录【一个点及其子树完全被包含的点】和【子树不完全被包含的点】,为了方便查询,第一个数组里储存那个点的线段树的根节点,第二个数组里储存那个点的值,顺便再将k–,这样就不用考虑它自己了,在二分时就只需要考虑左子树大小就好了。查询时进行二分,l<r,由于线段树的两个端点和我们二分的边界完全一致,所以对于第一个数组,每次直接加上每颗线段树上的左儿子的size,而对于第二个数组,遍历一遍判断是否在区间内,加上就好了。计算完我们目前二分的权值内的点数后,如果大于我们要找的k个,说明答案在左边,r=mid,线段树上往左走,也就是第一个数组内地点全都变成它的左儿子。否则的话,说明在右边,l=mid+1,k-=点数,线段树的点也往右儿子走一下。当l==r时,就相当于找到了那个点,最后的l或者r就是答案。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注