#163. 「带修改区间第k大」Dynamic Rankings

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

题目描述

给定一个含有 n 个数的序列 \{ a_1, a_2, a_3 \ldots, a_n \} ,程序必须回答这样的询问:对于给定的 l r k ,在 \{ a_l, a_{l + 1}, a_{l + 2}, \ldots a_r \} 中第 k 小的数是多少,并且,你可以改变一些 a_i 的值,改变后,程序还能针对改变后的 a 继续回答上面的问题。你需要编一个这样的程序,从输入文件中读入序列 a ,然后读入一系列的指令,包括询问指令和修改指令。对于每一个询问指令,你必须输出正确的回答。

输入格式

第一行有两个正整数 n m 。分别表示序列的长度和指令的个数。
第二行有 n 个数,表示序列 a ,这些数都小于 10 ^ 9 。接下来的 m 行描述每条指令,每行的格式是下面两种格式中的一种。

  • Q l r k 表示询问指令,询问 \{ a_l, a_{l + 1}, a_{l + 2}, \ldots a_r \} 中第 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 \leq n \leq 10000, 1 \leq m \leq 10000, 0 \leq t \leq 10 ^ 9