区间查询
测试数据来自 system/1665
背景
JZP神牛看到了一道题,觉得太水了,于是交给yxyddd做,yxyddd也觉得太水了,把这题交给了yxy,yxy是个沙茶,根本没想法。所以这个只能交给你了。
描述
一个长度为n的序列,支持两种操作:
1.输出[A, B]区间第k小的数(从小到大排序后第k个)
2.修改第I个数为W
格式
输入格式
第一行两个整数N(1<=N<=50000),M(1<=M<=10000),表示有N个数,M个操作
第二行N个数AI
以下M行,每行一个操作
Q i j k(查询[I,J]中第k小的数)或 C i W(把第I个数改成W)
输出格式
对于每个查询操作,输出每个查询结果
样例1
样例输入1
5 3
1 2 3 4 5
Q 1 4 2
C 2 5
Q 1 4 2
样例输出1
2
3
限制
1s
提示
经典题目