Dynamic Rankings

题目描述

给定一个含有 $n$ 个数的序列 $a_1,a_2 \dots a_n$,需要支持两种操作: - `Q l r k` 表示查询下标在区间 $[l,r]$ 中的第 $k$ 小的数 - `C x y` 表示将 $a_x$ 改为 $y$

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

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

输出样例 #1

3
6

说明

【数据范围】 对于 $10\%$ 的数据,$1\le n,m \le 100$; 对于 $20\%$ 的数据,$1\le n,m \le 1000$; 对于 $50\%$ 的数据,$1\le n,m \le 10^4$; 对于 $100\%$ 的数据,$1\le n,m \le 10^5$,$1 \le l \le r \le n$,$1 \le k \le r-l+1$,$1\le x \le n$,$0 \le a_i,y \le 10^9$。 请注意常数优化,但写法正常的整体二分和树套树都可以以大约 $1000\text{ms}$ 每个点的时间通过。 来源:bzoj1901 本题数据为洛谷自造数据,使用[CYaRon](https://github.com/luogu-dev/cyaron)耗时5分钟完成数据制作。