#P2488. 树套树-简单版
树套树-简单版
2488. 树套树-简单版(线段树套平衡树)
题目描述
请你写出一种数据结构,来维护一个长度为 的序列,其中需要提供以下操作:
1 pos x,将pos位置的数修改为 。2 l r x,查询整数 在区间 内的前驱(前驱定义为小于 ,且最大的数)。
数列中的位置从左到右依次标号为 。
区间 表示从位置 到位置 之间(包括两端点)的所有数字。
输入格式
第一行包含两个整数 和 。
第二行包含 个整数,表示有序数列。
接下来 行,每行包含一个操作指令,格式如题目所述。
输出格式
对于所有操作 2,每个操作输出一个查询结果,每个结果占一行。
数据范围
, , , ,
有序数列中的数字始终满足在 范围内,
数据保证所有操作一定合法,所有查询一定有解。
输入样例
5 3
3 4 2 1 5
2 2 4 4
1 3 5
2 2 4 4
输出样例
2
1