题目描述

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

  1. 查询 kk 在区间内的排名

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

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

  4. 查询 kk 在区间内的前驱(前驱定义为严格小于 xx,且最大的数)

  5. 查询 kk 在区间内的后继(后继定义为严格大于 xx,且最小的数)

输入格式

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

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

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

opt=1opt=1,则为操作 11,之后有三个数 l r kl~r~k,表示查询 kk 在区间 [l,r][l,r] 的排名。

opt=2opt=2,则为操作 22,之后有三个数 l r kl~r~k,表示查询区间 [l,r][l,r] 内排名为 kk 的数。

opt=3opt=3,则为操作 33,之后有两个数 pos kpos~k,表示将 pospos 位置的数修改为 kk

opt=4opt=4,则为操作 44,之后有三个数 l r kl~r~k,表示查询区间 [l,r][l,r]kk 的前驱。

opt=5opt=5,则为操作 55,之后有三个数 l r kl~r~k,表示查询区间 [l,r][l,r]kk 的后继。

输出格式

对于操作 1,2,4,51,2,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

提示说明

1n,m5×1041\le n,m\le5\times 10^4,序列中的值在任何时刻 [0,108]\in[0,10^8]

0 条评论

目前还没有评论...

信息

ID
3196
时间
1000ms
内存
256MiB
难度
(无)
标签
(无)
递交数
0
已通过
0
上传者