{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv id\u003d\"problem-body\"\u003e\n\t\n\u003ctable class\u003d\"problems\" width\u003d\"100%\"\u003e\u003ctbody\u003e\u003ctr class\u003d\"navigation\"\u003e\n\u003ctd width\u003d\"50%\"\u003e\u003ca href\u003d\"https://www.spoj.com/problems/MKTHNUM/en/\"\u003e英语\u003c/a\u003e\u003c/td\u003e \n\u003ctd width\u003d\"50%\"\u003e\u003ca href\u003d\"https://www.spoj.com/problems/MKTHNUM/vn/\"\u003e越南语\u003c/a\u003e\u003c/td\u003e \n\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\n\n\n\u003cp\u003e \u003c/p\u003e\n\u003cp\u003e你正在Macrohard公司的数据结构部门工作。在上一次关于键插入的任务失败后,你被要求编写一个新的数据结构,能够快速返回数组段中的第k个顺序统计量。\u003c/p\u003e\n\u003cp\u003e也就是说,给定一个由不同整数数组a[1 ... n],你的程序必须回答一系列形式为Q(i, j, k)的问题:\"如果对这个段进行排序,a[i ... j]段中的第k个数字是多少?\"\u003c/p\u003e\n\u003cp\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。\u003c/p\u003e\n\u003ch3\u003e输入\u003c/h3\u003e\n\u003cp\u003e输入的第一行包含n — 数组的大小,m — 要回答的问题的数量 (1 ≤ n ≤ 100000, 1 ≤ m ≤ 5000)。\u003c/p\u003e\n\u003cp\u003e第二行包含n个不超过10^9的不同整数,表示要给出答案的数组。\u003c/p\u003e\n\u003cp\u003e接下来的m行包含问题描述,每个描述由三个数字组成:i, j, 和 k (1 ≤ i ≤ j ≤ n, 1 ≤ k ≤ j - i + 1),表示问题Q(i, j, k)。\u003c/p\u003e\n\u003ch3\u003e输出\u003c/h3\u003e\n\u003cp\u003e对于每个问题,输出它的答案 — 排序后的a[i ... j]段中的第k个数字。\u003c/p\u003e\n\u003ch3\u003e示例\u003c/h3\u003e\n\u003cdiv\u003e\u003ctable class\u003d\"vjudge_sample\"\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\r\n\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e5\r\n6\r\n3\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/div\u003e\n\n\u003cp\u003e注意:朴素的解决方案行不通!!!\u003c/p\u003e\n\n\n \n\u003c/div\u003e"}}]}