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

    给定一个由N个数组成的序列{A1,A2,...,AN}
    每次提问(l,r,k)表示提问序列中{Al,..,Ar}中第k小的数的值。

    输入格式

    第一行两个数N,Q,表示有N个数,Q次提问。
    第二行N个数,为给定的序列。
    接下来Q行每行三个数(l,r,k),表示提问。

    输出格式

    对每个提问输出一行,只有一个数,为对应的答案。

    样例输入

    7 3
    1 5 2 6 3 7 4
    2 5 3
    4 4 1
    1 7 3

    样例输出

    5
    6
    3

    提示

    对于40%的数据
    1<=N<=1000
    1<=Q<=1000

    对于60%的数据(包含上述40%的数据),Ai是1到N的一个排列

    对于100%的数据
    1<=N<=100000
    1<=Q<=200000
    1<=Ai<=2*109
    1<=k<=r-l+1


    来源  感谢nodgd提供数据 题解