3404. 不是最小的,也是很小的

单点时限: 2.0 sec

内存限制: 256 MB

没有 Description 也是很小的!

输入格式

第一行一个整数 $T$ $(1 \leq T \leq 5)$。

接下来 $T$ 组数据,每组数据格式如下:

第一行一个整数 $n$ $(1\leq n \leq10^4)$。

第二行 $n$ 个整数,表示 $a_1, a_2, \ldots, a_n$ $(1 \leq a_i\leq10^4)$。

第三行一个整数 $q$ $(1\leq q\leq10^4)$,表示有 $q$ 次询问。

接下来 $q$ 行,可能有以下两种:

  • 0 l r k $(1\leq l\leq r\leq n, 1\leq k\leq r-l+1)$,分别表示区间左端点、右端点,第 $k$ 小。
  • 1 p v $(1\leq p \leq n, 1\leq v \leq 10^4)$,把 $a_p$ 改为 $v$。

输出格式

对于第一种询问,输出一个整数,表示 $a_l, a_{l+1}, \ldots, a_r$ 中第 $k$ 小的数。

样例

Input
2
2
1 2
2
0 1 2 1
0 1 2 2
4
4 3 2 1
4
0 1 1 1
1 1 1
0 1 1 1
0 1 4 3
Output
1
2
4
1
2

4 人解决,11 人已尝试。

6 份提交通过,共有 40 份提交。

8.6 EMB 奖励。

创建: 2 年,11 月前.

修改: 2 年,10 月前.

最后提交: 1 年,5 月前.

来源: N/A