#P42400. 【模板】树套树1/二逼平衡树
【模板】树套树1/二逼平衡树
题目链接
题目描述
您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:
-
查询 在区间内的排名
-
查询区间内排名为 的值
-
修改某一位值上的数值
-
查询 在区间内的前驱(前驱定义为严格小于 ,且最大的数,若不存在输出
-2147483647
) -
查询 在区间内的后继(后继定义为严格大于 ,且最小的数,若不存在输出
2147483647
)
输入格式
第一行两个数 ,表示长度为 的有序序列和 个操作。
第二行有 个数,表示有序序列。
下面有 行, 表示操作标号。
若 ,则为操作 ,之后有三个数 ,表示查询 在区间 的排名。
若 ,则为操作 ,之后有三个数 ,表示查询区间 内排名为 的数。
若 ,则为操作 ,之后有两个数 ,表示将 位置的数修改为 。
若 ,则为操作 ,之后有三个数 ,表示查询区间 内 的前驱。
若 ,则为操作 ,之后有三个数 ,表示查询区间 内 的后继。
输出格式
对于操作 ,各输出一行,表示查询结果。
9 6
4 2 2 1 9 4 0 1 1
2 1 4 3
3 4 10
2 1 4 3
1 2 5 9
4 3 9 5
5 2 8 5
2
4
3
4
9
提示
,序列中的值在任何时刻 。
题目来源:bzoj3196 / Tyvj1730 二逼平衡树,在此鸣谢。
此数据为洛谷原创。(特别提醒:此数据不保证操作 4、5 一定存在,故请务必考虑不存在的情况。)