BZOJ3196 Tyvj 1730 二逼平衡树

题目大意

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

题解

我过的第一题树套树吧QWQ

第一维用区间线段树,第二维用权值线段树,开始要离散化

第一个操作就是求和

第二个操作二分

第三个操作是修改

第四五个操作可以直接用一二两个操作来实现

好吧就是一道裸题,但有点难写

代码

2 条评论
  1. Thanks a lot for providing individuals with an extremely splendid chance to read from this blog. It’s always so great plus stuffed with a good time for me personally and my office acquaintances to visit your site no less than thrice in a week to see the latest guides you will have. Not to mention, I’m also certainly pleased with the outstanding principles served by you. Some two facts in this posting are particularly the most beneficial I have ever had.

发表一条评论