#515. 「愚人节欢乐赛 2019」Woshiluo 的主席树

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Woshiluo

题目描述

Woshiluo 正一如既往的做着水题,休息时修复着 NovaOJ 的各种锅

忽然,Woshiluo 的双肩被手搭住

「出题啦!Woshiluo」StudyingFather 说道

出题什么的关开发组什么事情,Woshiluo 如此想到

但毕竟对方是比自己大两个学年的学长,还是尊敬一下的

Woshiluo 想先做完手上这道带修主席树,再去出题,你能帮 Woshiluo 做一下吗?

求区间第 k

输入格式

第一行两个数字 n , m 表示有一个长度为 n 的数列,有 m 次操作

第二行 n 个数字,表示数列中各项的数字

接下来 m 行,每行第一个数字 op 表示操作类型

  • op = 1 时,接下来三个数字 l,r,k ,表示查询区间 [l,r] 的第 k 大数
  • op = 2 时,接下来两个数字 x,y , 表示将第 x 个数字变为 y x 无效时忽略此操作

输出格式

对于每个 op = 1 输出一个数字,表示查询结果

样例

样例输入

5 5
25957 6405 15770 26287 26465 
1 2 2 1
1 3 4 1
1 4 5 1
1 1 2 2
1 4 4 1

样例输出

6405
15770
26287
25957
26287

数据范围与提示

op \in [1,2]

1 \leq n,m \leq 2 \times 10^5

-10^9 \leq a_i ,y\leq 10^9

1 \leq l,r \leq n

x \leq n