TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2670
  • 题目
  • P2670动态区间第K小数
    限制 : 时间限制 : 50000 MS   空间限制 : 543210 KB
    问题描述

    给定一个由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


    来源  感谢nodgd提供数据