TYVJ1730 二逼平衡树 线段树+Treap

发布于 2017-07-12  2.45k 次阅读


[toggle hide="yes" title="题目" color=""]

【题目描述】

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

【输入格式】

第一行两个数 n,m 表示长度为n的有序序列和m个操作
第二行有n个数,表示有序序列
下面有m行,opt表示操作标号
若opt=1 则为操作1,之后有三个数l,r,k 表示查询k在区间[l,r]的排名
若opt=2 则为操作2,之后有三个数l,r,k 表示查询区间[l,r]内排名为k的数
若opt=3 则为操作3,之后有两个数pos,k 表示将pos位置的数修改为k
若opt=4 则为操作4,之后有三个数l,r,k 表示查询区间[l,r]内k的前驱
若opt=5 则为操作5,之后有三个数l,r,k 表示查询区间[l,r]内k的后继

【输出格式】

对于操作1,2,4,5各输出一行,表示查询结果

【样例输入】

【样例输出】

【提示】

n,m<=50000   保证有序序列所有值在任何时刻满足[0,10^8]

[/toggle]

树套树第一题!一共搞了仨小时= =

先调好一个正常的Treap,可以封装一下,再去搞嵌套,这样会很好调试。

对[1,n]建立线段树,每个节点对应一颗Treap,初始时,在线段树中,将区间中的每个点都插入对应的Treap

查询区间排名:线段树分解,查询区间中比该数小的有多少。

查询区间K小:二分答案,判断区间中是否存在符合要求的数。注意:二分时可能会遇到重复的节点,可以查询严格小于M的数有多少,然后用类似“最小值最大”的二分搞,这里的细节比较多。

单点修改:线段树分解,删掉原数插入新数。

区间前驱后继:线段树分解后,取前驱后继中最小、最大。

代码:

 


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974