{"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":"\n\u003cdiv id\u003d\"problem-body\"\u003e\n \u003ctable class\u003d\"problems\" width\u003d\"100%\"\u003e\n \u003ctbody\u003e\n \u003ctr class\u003d\"navigation\"\u003e\n \u003ctd width\u003d\"50%\"\u003e\u003ca href\u003d\"https://www.spoj.com/problems/MKTHNUM/en/\"\u003eTiếng Anh\u003c/a\u003e\u003c/td\u003e\n \u003ctd width\u003d\"50%\"\u003e\u003ca href\u003d\"https://www.spoj.com/problems/MKTHNUM/vn/\"\u003eTiếng Việt\u003c/a\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\n \u003c/table\u003e\n \u003cp\u003e\u003c/p\u003e\n \u003cp\u003eBạn đang làm việc cho công ty Macrohard trong bộ phận cấu trúc dữ liệu. Sau khi thất bại trong nhiệm vụ trước về việc chèn khóa, bạn được yêu cầu viết một cấu trúc dữ liệu mới có khả năng trả về nhanh chóng thống kê thứ tự k trong đoạn mảng.\u003c/p\u003e\n \u003cp\u003eNghĩa là, cho một mảng a[1 ... n] gồm các số nguyên khác nhau, chương trình của bạn phải trả lời một loạt câu hỏi Q(i, j, k) theo dạng: \"Số thứ k trong đoạn a[i ... j], nếu đoạn này được sắp xếp thì sẽ là số nào?\"\u003c/p\u003e\n \u003cp\u003eVí dụ, xem xét mảng a \u003d (1, 5, 2, 6, 3, 7, 4). Hãy cho câu hỏi Q(2, 5, 3). Đoạn a[2 ... 5] là (5, 2, 6, 3). Nếu chúng ta sắp xếp đoạn này, chúng ta sẽ có (2, 3, 5, 6), số thứ ba là 5, và do đó câu trả lời cho câu hỏi là 5.\u003c/p\u003e\n \u003ch3\u003eNhập\u003c/h3\u003e\n \u003cp\u003eDòng đầu tiên của đầu vào chứa n - kích thước của mảng, và m - số câu hỏi cần trả lời (1 ≤ n ≤ 100000, 1 ≤ m ≤ 5000).\u003c/p\u003e\n \u003cp\u003eDòng thứ hai chứa n số nguyên khác nhau không vượt quá 10^9 theo giá trị tuyệt đối - mảng cho các câu trả lời.\u003c/p\u003e\n \u003cp\u003eM dòng tiếp theo chứa các mô tả câu hỏi, mỗi mô tả bao gồm ba số: i, j và k (1 ≤ i ≤ j ≤ n, 1 ≤ k ≤ j - i + 1) và đại diện cho câu hỏi Q(i, j, k).\u003c/p\u003e\n \u003ch3\u003eXuất\u003c/h3\u003e\n \u003cp\u003eĐối với mỗi câu hỏi, xuất câu trả lời cho nó - số thứ k trong đoạn a[i ... j] đã sắp xếp.\u003c/p\u003e\n \u003ch3\u003eVí dụ\u003c/h3\u003e\n \u003cdiv\u003e\n \u003ctable class\u003d\"vjudge_sample\"\u003e\n \u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eNhập\u003c/th\u003e\n \u003cth\u003eXuất\u003c/th\u003e\n \u003c/tr\u003e\n \u003c/thead\u003e\n \u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\n \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\n \u003cpre\u003e5\r\n6\r\n3\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\n \u003c/table\u003e\n \u003c/div\u003e\n \u003cp\u003eLưu ý: một giải pháp ngây thơ sẽ không hoạt động!!!\u003c/p\u003e\n\u003c/div\u003e"}}]}