#2555. 动态区间问题

动态区间问题

Description

写一种数据结构(平 衡树)来维护一个有序数列,其中需要提供以下操作:

①查询kk 在区间 内的排名;

②查询区间内排名为kk 的值;

③修改某一位置上的数值;

④ 查询kk 在区间内的前驱(前驱指严格小于xx 且最大的数,若不存在,则 输出2147483647-2147483647);

⑤查询kk 在区间内的后继(后继指严格大于xx 且 最小的数,若不存在,则输出21474836472147483647)。

Format

Input

11行包含两个整数nmn 、m ,表示序列元素数量和操作数 量。

22行包含nn 个数,表示有序序列。

接下来的mm 行,optopt表示操作标 号,

opt=1opt=1,则为操作①,之后有33个数lrkl 、r 、k ,表示查询kk[l,r][l, r ]区间的排名;

opt=2opt=2,则为操作②,之后有33个数lrkl、r、k ,表 示查询[l,r][l , r ]区间排名为kk 的数;

opt=3opt=3,则为操作③,之后有两 个数poskpos、k ,表示将pospos位置的数修改为kk

opt=4opt=4,则为操作④, 之后有33个数lrkl、r、k ,表示查询[l,r][l , r ]区间kk 的前驱;

opt=5opt=5,则 为操作⑤,之后有33个数lrkl、r、k ,表示查询[l,r][l , r ]区间kk 的后继。n,m5×104n, m ≤5×10^4 ,保证有序序列的所有值在任何时刻都满足[0,108][0, 10^8]

Output

对操作①②④⑤各输出一行,表示查询结果。

Samples

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

来源

P3380/bzoj3196/Tyvj1730