#O1107. 带修改的区间第 k 小
带修改的区间第 k 小
题目描述
给定长度为 的整数序列 ,支持两种操作:
- 询问区间 中第 小的数;
- 把 修改为 。
输入格式
第一行两个整数 。
第二行 个整数 。
接下来 行,每行为以下两种之一:
0 p x:把 修改为 ;1 l r k:询问区间 中第 小的数。
输出格式
对每个询问操作,输出一行一个整数表示答案。
样例 #1
样例输入 #1
5 3
1 3 2 5 4
1 1 5 2
0 2 6
1 1 3 2
样例输出 #1
2
2
数据规模与约定
| 数据范围 | 说明 |
|---|---|
| 序列长度与操作数 | |
| 数值范围 | |
| 询问区间 | |
| 询问排名 |
- 询问保证合法。
- 建议使用整体二分或树套树,单次询问复杂度 。