#332. 1901. Zju2112 Dynamic Rankings

1901. Zju2112 Dynamic Rankings

Dynamic Rankings

题目描述

给定一个含有 nn 个数的序列 a1,a2ana_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,a2ana_1,a_2 \dots a_n。 接下来 mm 行,每行表示一个操作,都为上述两种中的一个。

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

3
6

提示

【数据范围】

对于 10%10\% 的数据,1n,m1001\le n,m \le 100; 对于 20%20\% 的数据,1n,m10001\le n,m \le 1000; 对于 50%50\% 的数据,1n,m1041\le n,m \le 10^4; 对于 100%100\% 的数据,1n,m1051\le n,m \le 10^51lrn1 \le l \le r \le n1krl+11 \le k \le r-l+11xn1\le x \le n0ai,y1090 \le a_i,y \le 10^9

请注意常数优化,但写法正常的整体二分和树套树都可以以大约 1000ms1000\text{ms} 每个点的时间通过。

来源:bzoj1901