#2185. Dynamic Rankings

    ID: 2185 传统题 1000ms 512MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>数据结构树套树可持久化线段树算法竞赛进阶指南

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
  • 洛谷P2617
  • 算法竞赛进阶指南