#O1107. 带修改的区间第 k 小

带修改的区间第 k 小

题目描述

给定长度为 nn 的整数序列 aa,支持两种操作:

  1. 询问区间 [l,r][l,r] 中第 kk 小的数;
  2. 把 apa_p 修改为 xx。

输入格式

第一行两个整数 n,Qn,Q。

第二行 nn 个整数 a1,…,ana_1,\dots,a_n。

接下来 QQ 行,每行为以下两种之一:

  • 0 p x:把 apa_p 修改为 xx;
  • 1 l r k:询问区间 [l,r][l,r] 中第 kk 小的数。

输出格式

对每个询问操作,输出一行一个整数表示答案。

样例 #1

样例输入 #1

5 3
1 3 2 5 4
1 1 5 2
0 2 6
1 1 3 2

样例输出 #1

2
2

数据规模与约定

数据范围 说明
1≤n,Q≤1051 \le n,Q \le 10^5 序列长度与操作数
1≤ai,x≤1091 \le a_i,x \le 10^9 数值范围
1≤l≤r≤n1 \le l \le r \le n 询问区间
1≤k≤r−l+11 \le k \le r-l+1 询问排名
  • 询问保证合法。
  • 建议使用整体二分或树套树,单次询问复杂度 O(log⁡2n)O(\log^2 n)。