logo AlgoBeat OnlineJudge
登录 注册

#118. 【模板】树套树

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

题目描述

这是一道模板题。

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

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

输入格式

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

下面有 行,每行第一个数表示操作类型:

1.之后有三个数 表示查询 在区间 的排名;
2.之后有三个数 表示查询区间 内排名为 的数;
3.之后有两个数 表示将 位置的数修改为
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

数据范围与提示

,保证 存在前驱和后继。