题目描述

您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：

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\le n,m\le5\times 10^4$，序列中的值在任何时刻 $\in[0,10^8]$

题目来源：bzoj3196 / Tyvj1730 二逼平衡树，在此鸣谢

此数据为洛谷原创。（特别提醒：此数据不保证操作4、5一定存在，故请务必考虑不存在的情况）

## 题目描述

您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：

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\le n,m\le5\times 10^4$，序列中的值在任何时刻  $\in[0,10^8]$

题目来源：bzoj3196 / Tyvj1730 二逼平衡树，在此鸣谢

此数据为洛谷原创。**（特别提醒：此数据不保证操作4、5一定存在，故请务必考虑不存在的情况）**

@SSerxhs