同洛谷 P3380 【模板】树套树

[AdditionalFile106.zip](file://AdditionalFile106.zip?type=additional_file)

#106. 二逼平衡树

题目描述

这是一道模板题。

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

1. 查询 $x$ 在区间内的排名；
2. 查询区间内排名为 $k$ 的值；
3. 修改某一位置上的数值；
4. 查询 $x$ 在区间内的前驱（前驱定义为小于 $x$，且最大的数）；
5. 查询 $x$ 在区间内的后继（后继定义为大于 $x$，且最小的数）。

输入格式

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

下面有 $m$ 行，每行第一个数表示操作类型：

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

输出格式

对于操作 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 \le n, m \le 5 \times 10^4, 0 \le a_i, y \le 10^8, 1 \le l \le r \le n, 1 \le pos \le n, 1 \le k \le r - l + 1, -10^8 \le x \le 10^8$，保证 $x$ 存在前驱和后继。4.查询k在区间内的前驱(前驱定义为小于x，且最大的数)
    5.查询k在区间内的后继(后继定义为大于x，且最小的数)
【输入格式】
    第一行两个数 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的前驱(前驱定义为严格小于x，且最大的数，若不存在输出-2147483647)