/ FtOJ / 题库 /

「模板」二逼平衡树

「模板」二逼平衡树

暂无测试数据。

Description

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

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

Format

Input

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

第二行有 \(n\) 个数,表示有序序列。

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

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

Output

对于操作 \(1,2,4,5\) 各输出一行,表示查询结果。

Sample 1

Input

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

Output

2
4
3
4
9

Limitation

Data

\( 1 \leq n, m \leq 5 \times 10 ^ 4, -10 ^ 8 \leq k, x \leq 10 ^ 8 \)

Time and Space

4s, 256MB.

Source

loj #106

update by Shuchong

信息

ID
1004
难度
(无)
分类
平衡树 点击显示
标签
递交数
1
已通过
0
通过率
0%
上传者