题目名称	257. 动态排名系统
输入输出	`dynrank.in/out`
难度等级	★★★★
时间限制	5000 ms (5 s)
内存限制	512 MiB
测试数据	10
题目来源	BYVoid 于2009-02-08加入
开放分组	全部用户
提交状态
分类标签	分治平衡树线段树可持久化线段树可持久化 CDQ分治整体分治树套树
	分享题解

通过：317，提交：898，通过率：35.3%
Xlayton	100	0.280 s	7.22 MiB	C++
Cooook	100	0.311 s	95.29 MiB	C++
Troywar	100	0.315 s	95.29 MiB	C++
new ioer	100	0.322 s	13.91 MiB	C++
Go灬Fire	100	0.340 s	5.45 MiB	C++
Gitfan	100	0.345 s	95.29 MiB	C++
ACalvin	100	0.357 s	4.56 MiB	C++
yrtiop	100	0.384 s	40.60 MiB	C++
Marvolo	100	0.384 s	42.44 MiB	C++
f0rest	100	0.388 s	70.25 MiB	C++

关于动态排名系统的近10条评论(全部评论)
数组开大点就过了。。。神奇 yrtiop 2021-06-20 22:49 37楼
线段树套平衡树 hyghb 2018-01-06 16:10 36楼
忘了更改null的lc,rc。。。。为什么你们那么快啊QAQ Hzoi_QTY 2017-10-01 06:07 35楼
rch打成lch 改了我一个晚上 Hzoi_Mafia 2017-09-28 19:42 34楼
Cooook 2017-07-31 16:07 33楼
回复 @Cydiater : 这题的数据导致了整体二分丧失优势，要想对比速度，可以用 @1345.K大��查询来比较，亲测相差10倍以上 _Itachi 2017-02-14 06:03 32楼
都说整体二分快，为什么比我写的主席树还要慢啊 Cydiater 2017-02-13 21:18 31楼
树状数组套主席树整体二分线段树套平衡树 Go灬Fire 2017-02-12 21:17 30楼
一发线段树套avl..迷啊..这个题把maintain函数改个名字也过了... sxysxy 2016-10-17 19:14 29楼
第一发整体二分！ _Itachi 2016-10-04 20:20 28楼

257. 动态排名系统

★★★★ 输入文件：dynrank.in 输出文件：dynrank.out 简单对比
时间限制：5 s 内存限制：512 MiB

【问题描述】

给定一个长度为N的已知序列A[i](1<=i<=N)，要求维护这个序列，能够支持以下两种操作：
1、查询A[i],A[i+1],A[i+2],...,A[j](1<=i<=j<=N)中，升序排列后排名第k的数。
2、修改A[i]的值为j。

所谓排名第k，指一些数按照升序排列后，第k位的数。例如序列{6,1,9,6,6}，排名第3的数是6，排名第5的数是9。

【输入格式】

第一行包含一个整数D(0<=D<=4)，表示测试数据的数目。接下来有D组测试数据，每组测试数据中，首先是两个整数N(1<=N<=50000),M(1<=M<=10000)，表示序列的长度为N，有M个操作。接下来的N个不大于1,000,000,000正整数，第i个表示序列A[i]的初始值。然后的M行，每行为一个操作
Q i j k 或者
C i j
分别表示查询A[i],A[i+1],A[i+2],...,A[j](1<=i<=j<=N)中，升序排列后排名第k的数，和修改A[i]的值为j。

【输出格式】

对于每个查询，输出一行整数，为查询的结果。测试数据之间不应有空行。

【样例输入】

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

【样例输出】

3
6
3
6