[BZOJ3196/Luogu3380]二逼平衡树(树套树,线段树)

发布于 2018-04-17  250 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ3196/Luogu3380]二逼平衡树(树套树,线段树)

Description

您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:
1.查询k在区间内的排名
2.查询区间内排名为k的值
3.修改某一位值上的数值
4.查询k在区间内的前驱(前驱定义为小于x,且最大的数)
5.查询k在区间内的后继(后继定义为大于x,且最小的数)

Tag

树套树,线段树

解决思路

值域线段树套位置线段树的做法,对于每一种操作分别处理。至于求严格前驱和严格后继,可以用求区间内某值域范围内的数的个数来解决

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ3196/Luogu3380]二逼平衡树(树套树,线段树)


HNCJ OIer