#P3380. 【模板】树套树

【模板】树套树

题目描述

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

  1. 查询 kk 在区间内的排名

  2. 查询区间内排名为 kk 的值

  3. 修改某一位置上的数值

  4. 查询 kk 在区间内的前驱(前驱定义为严格小于 xx,且最大的数,若不存在输出 -2147483647

  5. 查询 kk 在区间内的后继(后继定义为严格大于 xx,且最小的数,若不存在输出 2147483647

输入格式

第一行两个数 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,各输出一行,表示查询结果。

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

提示

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

题目来源:bzoj3196 / Tyvj1730,在此鸣谢。

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