SP3946 MKTHNUM - K-th Number

[English](/problems/MKTHNUM/en/) [Vietnamese](/problems/MKTHNUM/vn/) 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.

N/A

N/A