中文
日本語
English
| P2670动态区间第K小数 | |
|
问题描述
给定一个由N个数组成的序列{A1,A2,...,AN}
每次可以将Ak的值改为t，或者提问序列中{Al,..,Ar}中第k小的数的值。
输入格式
第一行两个正整数N,M，表示有N个数，M次操作
接下来每行描述一个操作：
·如果第一个字符时C，那么接下来两个正整数k,t，表示把Ak的值改成t；
·如果第一个字符时Q，那么接下来三个正整数l,r,k，表示提问序列中{Al,..,Ar}中第k小的数的值。
输出格式
对每次提问输出一行，为改次提问的答案。
样例输入 1
7 5
1 3 2 4 3 5 6
Q 2 5 3
Q 1 4 4
C 3 7
Q 2 5 3
Q 1 4 4
样例输出 1
3
4
4
7
样例输入 2
50 50
50 69 16 48 59 77 66 94 36 4 78 14 63 97 55 44 2 39 74 81 80 26 95 66 98 36 86 66 42 74 15 20 55 20 42 74 63 52 91 32 100 39 44 42 84 31 70 53 20 23
C 1 99
Q 45 46 1
C 28 53
Q 37 45 5
C 26 49
C 19 43
C 24 49
Q 47 49 1
C 46 11
Q 44 46 2
Q 4 41 34
C 32 98
C 38 88
C 4 17
Q 47 50 1
Q 49 49 1
Q 33 36 1
Q 10 28 11
C 15 4
Q 50 50 1
C 29 89
C 42 68
Q 17 41 12
C 3 30
C 22 31
C 46 54
C 46 93
Q 6 27 17
Q 21 38 12
C 17 21
C 41 21
Q 25 25 1
Q 9 26 3
Q 1 2 1
C 39 61
C 39 52
C 12 22
C 9 95
C 38 94
Q 14 25 1
C 9 14
C 28 52
C 24 28
Q 27 43 5
Q 15 37 8
C 50 60
Q 4 16 1
Q 25 50 10
Q 26 41 6
Q 5 32 14
样例输出 2
31
52
20
42
94
20
20
20
55
23
55
81
80
98
14
69
4
42
42
4
52
49
59
提示
1<=N,M<=50000
初始状态1<=Ak<=50000
每次修改1<=k<=N，1<=t<=50000
每次提问1<=k<=r-l+1