1581_二逼平衡树

这是一道模板题。

您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：

1. 查询 x 在区间内的排名；

2. 查询区间内排名为 k 的值；

3. 修改某一位置上的数值；

4. 查询 x 在区间内的前趋（前趋定义为小于 x ，且最大的数）；

5. 查询 x 在区间内的后继（后继定义为大于 x ，且最小的数）。

第一行两个数 n, m 表示长度为 n 的有序序列和 m 个操作。

第二行有 n 个数，表示有序序列。

下面有 m 行，每行第一个数表示操作类型：

1. 之后有三个数 l,r,x 表示查询 x 在区间 [l,r] 的排名；

2. 之后有三个数 l,r,k 表示查询区间 [l,r] 内排名为 k 的数；

3. 之后有两个数 pos, x 表示将 pos 位置的数修改为 x ；

4. 之后有三个数 l,r,x 表示查询区间 [l,r] 内 x 的前趋；

5. 之后有三个数 l,r,x 表示查询区间 [l,r] 内 x 的后继。

1 ≤ n, m ≤ 5×10⁴  , −10⁸ ≤ k, x ≤ 10⁸

对于操作 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