#1067. Dynamic Rankings

Dynamic Rankings

题目描述

给定一个含有 nn 个数的序列 a1,a2…ana_1,a_2 \dots a_n,需要支持两种操作:

  • Q l r k 表示查询下标在区间 [l,r][l,r] 中的第 kk 小的数;
  • C x y 表示将 axa_x 改为 yy。

输入格式

第一行两个正整数 n,mn,m,表示序列长度与操作个数。
第二行 nn 个整数,表示 a1,a2…ana_1,a_2 \dots a_n。
接下来 mm 行,每行表示一个操作,都为上述两种中的一个。

输出格式

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

样例

5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3
3
6

题目来源:洛谷 P2617