TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Course  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P2664
  • Problem
  • P2664静态区间第K小数
    Limits : Time Limit : 40000 MS   Memory Limit : 234567 KB
    Description

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

    Input Format

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

    Output Format

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

    Sample Input

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

    Sample Output

    5
    6
    3

    Hint

    对于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


    Source  感谢nodgd提供数据 题解