• [J] Teemo

  • 时间限制: 3000 ms 内存限制: 65535 K
  • 问题描述
  • There are N noxious traps. The ith noxious trap contains Ni mushrooms.

    Teemo usually asks Amumu, "Do you know the Kth largest mushroom number during N[i..j]?".

  • 输入
  • There are muti-case.
    For each test case, the first line contains two integer N (0 < N < 100,000) and M (0 < M < 5,000) , N means the number of the nouxious trap, M means the times Teemo asked Amumu.
    The next line contains N integers, means ith noxious trap contains Ni mushrooms.
    The next M lines, for each line, there are three integers I, J, K (1 ≤ I ≤ J ≤ N, 1 ≤ K ≤ J - I + 1). I means the start trap number, J means the end trap number.
  • 输出
  • For each question that Teemo asked, you have to print the answer for a line.
  • 样例输入
  • 7 3
    1 5 2 6 3 7 4
    2 5 3
    4 4 1
    1 7 3
    
  • 样例输出
  • 5
    6
    3
    
  • 提示
  • 来源
  • Monkeyde17
  • 操作

显示春菜