#106. 二逼平衡树

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

题目描述

这是一道模板题。

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

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

输入格式

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

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

  1. 之后有三个数 l,r,x l, r, x l,r,x 表示查询 x x x 在区间 [l,r] [l, r] [l,r] 的排名;
  2. 之后有三个数 l,r,k l, r, k l,r,k 表示查询区间 [l,r] [l, r] [l,r] 内排名为 k k k 的数;
  3. 之后有两个数 pos,x \mathrm{pos}, x pos,x 表示将 pos \mathrm{pos} pos 位置的数修改为 x x x
  4. 之后有三个数 l,r,x l, r, x l,r,x 表示查询区间 [l,r] [l, r] [l,r]x x x 的前趋;
  5. 之后有三个数 l,r,x l, r, x l,r,x 表示查询区间 [l,r] [l, r] [l,r]x x x 的后继。

输出格式

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

数据范围与提示

1≤n,m≤5×104,−108≤k,x≤108 1 \leq n, m \leq 5 \times 10 ^ 4, -10 ^ 8 \leq k, x \leq 10 ^ 8 1n,m5×104,108k,x108