动态区间第k小 ### 题目描述 给定一个长度为 $N$ 的数组 $a$，其初值分别为 $a_1,a_2,...,a_N$。 现有 $Q$​ 个操作，每个操作可能为以下两种类型之一： + `1 x y`，令 $a_x=y$ + `2 l r k`，$a_l,a_{l+1},...,a_r$ 区间内第 $k$ 小的元素 请你编写程序完成这 $Q$ 个操作。 ### 输入描述 输入第 $1$ 行包含两个正整数 $N,Q$，分别表示数组 $a$ 的长度和查询的个数。 第 $2$ 行包含 $N$ 个非负整数 $a_1,a_2,...,a_N$，表示数组 $a$ 元素的初值。 第 $3\sim Q-2$ 行每行表示一个操作，格式为： + `1 x y`，令 $a_x=y$ + `2 l r k`，$a_l,a_{l+1},...,a_r$ 区间内第 $k$ 小的元素 $1\leq N,Q \leq 10^5$​，$1\leq l \leq r \leq N$​，$1\leq k \leq r-l+1$​，$1\leq x \leq N$，$1\leq y,a_i\leq 10^9$​。 ### 输出描述 对于每个查询操作，输出一行表示答案。 ### 输入输出样例 #### 示例 1 >输入 ```txt 5 3 1 2 3 4 5 2 1 5 3 1 3 5 2 1 5 3 ``` >输出 ```txt 3 4 ```