logo AlgoBeat OnlineJudge
登录 注册

#103196. [BZOJ 3196] Tyvj 1730 二逼平衡树

内存限制:128 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:

  1. 查询 在区间内的排名;
  2. 查询区间内排名为 的值;
  3. 修改某一位值上的数值;
  4. 查询 在区间内的前驱(前驱定义为严格小于 ,且最大的数);
  5. 查询 在区间内的后继(后继定义为严格大于 ,且最小的数)。

输入格式

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

第二行有 个数,表示有序序列。

下面有 行, 表示操作标号。

,则为操作 ,之后有三个数 ,表示查询 在区间 的排名。

,则为操作 ,之后有三个数 ,表示查询区间 内排名为 的数。

,则为操作 ,之后有两个数 ,表示将 位置的数修改为

,则为操作 ,之后有三个数 ,表示查询区间 的前驱。

,则为操作 ,之后有三个数 ,表示查询区间 的后继。

输出格式

对于操作 ,各输出一行,表示查询结果。

样例

样例输入 #1

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

样例输出 #1

2
4
3
4
9

数据范围与提示

对于所有数据,,序列中的值在任何时刻