题目描述
这是一道模板题。
您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：
查询
x
x 在区间内的排名；
查询区间内排名为
k
k 的值；
修改某一位置上的数值；
查询
x
x 在区间内的前趋（前趋定义为小于
x
x，且最大的数）；
查询
x
x 在区间内的后继（后继定义为大于
x
x，且最小的数）。
输入
第一行两个数
n, m
n,m，表示长度为
n
n 的有序序列和
m
m 个操作。
第二行有
n
n 个数，表示有序序列。
下面有
m
m 行，每行第一个数表示操作类型：
之后有三个数
l, r, x
l,r,x 表示查询
x
x 在区间
[l, r]
[l,r] 的排名；
之后有三个数
l, r, k
l,r,k 表示查询区间
[l, r]
[l,r] 内排名为
k
k 的数；
之后有两个数
\mathrm{pos}, x
pos,x 表示将
\mathrm{pos}
pos 位置的数修改为
x
x；
之后有三个数
l, r, x
l,r,x 表示查询区间
[l, r]
[l,r] 内
x
x 的前趋；
之后有三个数
l, r, x
l,r,x 表示查询区间
[l, r]
[l,r] 内
x
x 的后继。
输出
对于操作
1, 2, 4, 5
1,2,4,5 各输出一行，表示查询结果。
样例输入
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
提示
数据范围与提示
1 \leq n, m \leq 5 \times 10 ^ 4, -10 ^ 8 \leq k, x \leq 10 ^ 8
1≤n,m≤5×104,−108≤k,x≤108
来源/分类
平衡树 树套树 数据结构