【模板】二逼平衡树(树套树)

题目描述

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

  1. 查询 $k$ 在区间内的排名
  2. 查询区间内排名为 $k$ 的值
  3. 修改某一位值上的数值
  4. 查询 $k$ 在区间内的前驱(前驱定义为严格小于 $x$,且最大的数,若不存在输出 -2147483647
  5. 查询 $k$ 在区间内的后继(后继定义为严格大于 $x$,且最小的数,若不存在输出 2147483647

输入格式

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

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

下面有 $m$ 行,$opt$ 表示操作标号。

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

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

若 $opt=3$,则为操作 $3$,之后有两个数 $pos~k$,表示将 $pos$ 位置的数修改为 $k$。

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

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

输出格式

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

样例 #1