#P42300. 【模板】树套树2/Dynamic Rankings

    ID: 8 远端评测题 3000ms 512MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>数据结构树套树树状数组主席树*2300

【模板】树套树2/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 行,每行表示一个操作,都为上述两种中的一个。

输出格式

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

5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3
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

本题数据为洛谷自造数据,使用CYaRon耗时5分钟完成数据制作。