OpenJudge - 2104:K-th Number

2104:K-th Number

描述

You are working for Macrohard company in data structures department. After failing your previous task about key insertion you were asked to write a new data structure that would be able to return quickly k-th order statistics in the array segment.
That is, given an array a[1...n] of different integer numbers, your program must answer a series of questions Q(i, j, k) in the form: "What would be the k-th number in a[i...j] segment, if this segment was sorted?"
For example, consider the array a = (1, 5, 2, 6, 3, 7, 4). Let the question be Q(2, 5, 3). The segment a[2...5] is (5, 2, 6, 3). If we sort this segment, we get (2, 3, 5, 6), the third number is 5, and therefore the answer to the question is 5.

输入

The first line of the input file contains n --- the size of the array, and m --- the number of questions to answer (1 <= n <= 100 000, 1 <= m <= 5 000).
The second line contains n different integer numbers not exceeding 109 by their absolute values --- the array for which the answers should be given.
The following m lines contain question descriptions, each description consists of three numbers: i, j, and k (1 <= i <= j <= n, 1 <= k <= j - i + 1) and represents the question Q(i, j, k).

输出

For each question output the answer to it --- the k-th number in sorted a[i...j] segment.

第k个数字
描述：
你为了Macrohard公司的数据结构部门工作。在对关键插入的重要任务中失败了后，你被要求写一个新的数据结构，让它可以快速返回一个数据段中第k大的数。
那个意思是，给你一个有不同整数的数组a[1...n]，你的程序必须用这样的形式回答许多问题Q(i, j, k)：“什么是a[i...j]这个部分中第k大的数，如果这部分被排序了？”
例如，考虑这个数组a = (1, 5, 2, 6, 3, 7, 4)。我们让这个问题变成Q(2, 5, 3)。这个部分a[2...5] 是 (5, 2, 6, 3)。如果我们对这部分排序，我们得到了(2, 3, 5, 6)，第三大的数是5，并且因此这个问题的回答是5.
输入：
第一行输入包括n——这个数组的大小，和m——回答问题的数目(1 <= n <= 100 000, 1 <= m <= 5 000)。
第二行包括n个绝对值不超过10的9次方的不同整数——应该被给出答案的数组。
接下来m行包括问题描述，每个描述包括三个数字：i，j和k(1 <= i <= j <= n, 1 <= k <= j - i + 1)并且代表问题Q(i, j, k)。
输出：
对于每个问题输出他的答案——在a[i...j]这部分第k大的数。