#P3196. [模板题]Tyvj 1730 二逼平衡树

    ID: 2372 传统题 1000ms 512MiB 尝试: 6982 已通过: 1347 难度: 7 上传者: 标签>CF2300提高+/省选-线段树套平衡树Treap维护顺序统计量二分第 k 小难度分类

[模板题]Tyvj 1730 二逼平衡树

题目描述

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

  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

样例输入 #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

提示

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