luogu#P3380. 【模板】树套树
【模板】树套树
题目描述
您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:
- 查询 在区间内的排名;
- 查询区间内排名为 的值;
- 修改某一位置上的数值;
- 查询 在区间内的前驱(前驱定义为严格小于 ,且最大的数,若不存在输出
-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 一定存在,故请务必考虑不存在的情况。)