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

题目描述

您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作: 1. 查询k在区间内的排名 2. 查询区间内排名为k的值 3. 修改某一位值上的数值 4. 查询k在区间内的前驱(**前驱定义为严格小于x,且最大的数,若不存在输出-2147483647**) 5. 查询k在区间内的后继(**后继定义为严格大于x,且最小的数,若不存在输出2147483647**) #注意上面两条要求和tyvj或者bzoj不一样,请注意

输入输出格式

输入格式


第一行两个数 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

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

说明

时空限制:2s,128M $ n,m \leq 5\cdot {10}^4 $ 保证有序序列所有值在任何时刻满足 $ [0, {10} ^8] $ 题目来源:bzoj3196 / Tyvj1730 二逼平衡树,在此鸣谢 此数据为洛谷原创。(**特别提醒:此数据不保证操作4、5一定存在,故请务必考虑不存在的情况**)