{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"你正在Macrohard公司的数据结构部门工作。在之前的关于键插入的任务失败后,你被要求编写一个新的数据结构,该数据结构能够快速返回数组段中第k个顺序统计量。\n\u003cbr\u003e也就是说,给定一个由不同整数数组a[1...n],你的程序必须回答一系列形如Q(i, j, k)的问题:\"如果对该段进行排序,a[i...j]段中的第k个数字是多少?\"\n\u003cbr\u003e例如,考虑数组a \u003d (1, 5, 2, 6, 3, 7, 4)。假设问题是Q(2, 5, 3)。段a[2...5]是(5, 2, 6, 3)。如果对这个段进行排序,我们得到(2, 3, 5, 6),第三个数字是5,因此问题的答案是5。"}},{"title":"输入","value":{"format":"HTML","content":"输入文件的第一行包含n --- 数组的大小,以及m --- 要回答的问题数量 (1 \u0026lt;\u003d n \u0026lt;\u003d 100 000, 1 \u0026lt;\u003d m \u0026lt;\u003d 5 000)。\n\u003cbr\u003e第二行包含n个不超过10\u003csup\u003e9\u003c/sup\u003e的不同整数,表示应给出答案的数组。\n\u003cbr\u003e接下来的m行包含问题描述,每个描述由三个数字组成:i, j 和 k (1 \u0026lt;\u003d i \u0026lt;\u003d j \u0026lt;\u003d n, 1 \u0026lt;\u003d k \u0026lt;\u003d j - i + 1),表示问题Q(i, j, k)。"}},{"title":"输出","value":{"format":"HTML","content":"对于每个问题,输出答案 --- 排序后的a[i...j]段中的第k个数字。"}},{"title":"样例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e7 3\r\n1 5 2 6 3 7 4\r\n2 5 3\r\n4 4 1\r\n1 7 3\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e5\r\n6\r\n3\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"提示","value":{"format":"HTML","content":"这个问题的输入规模很大,所以请使用C风格的输入(scanf, printf),否则可能会超时。"}}]}