/ OIer TK / 题库 /

区间查询

区间查询

测试数据来自 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

提示

经典题目

信息

ID
1613
难度
(无)
分类
数据结构 | 树套树 点击显示
标签
(无)
递交数
0
已通过
0
通过率
?
上传者