Zju2112 Dynamic Rankings

给定一个含有 $n$ 个数的序列 $a_1, a_2, \dots, a_n$，你的程序必须回答这样的询问：对于给定的 $i, j, k$，求 $a_i, a_{i+1}, \dots, a_j$ 中第 $k$ 小的数是多少（$1\le k\le j-i+1$）。

并且，你可以改变某些 $a_i$ 的值。改变之后，程序还要能针对改变后的序列继续回答上面的问题。

输入格式

第一行两个正整数 $n, m$，分别表示序列的长度和指令的个数。

第二行 $n$ 个数，表示 $a_1, a_2, \dots, a_n$。

接下来 $m$ 行描述每条指令，每行是下面两种格式之一：

• Q i j k：询问指令，询问 $a_i, a_{i+1}, \dots, a_j$ 中第 $k$ 小的数；
• C i t：修改指令，把 $a_i$ 改变成 $t$。

输出格式

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

样例输入

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

样例输出

3
6

数据范围

• $1\le n\le 10^4$，$1\le m\le 10^4$；
• 初始序列中的数都小于 $10^9$；
• 询问指令满足 $1\le i\le j\le n$，$1\le k\le j-i+1$；
• 修改指令满足 $1\le i\le n$，$0\le t\le 10^9$。

来源与许可

本题为 ZJU 2112 试题「Dynamic Rankings」，题面与测试数据整理自 BZOJ 1901。