In this homework, you are asked to implement 2 functions.
1. QQ Inversion pairs count
2. K’s largest number
QQ Inversion pair
Let A be a sequence of numbers. (i, j) is an QQ inversion pair if i < j but A[i] > 2 * A[j].
For example: A = [1, 2, 3, 4], then A has no QQ inversion pair.
For example: B = [5, 4, 3, 2,1], B has 4 QQ inversion pairs:
(5, 2), (5, 1), (4, 1), (3, 1).
QQ Inversion pairs count
Output the number of inversion pairs
For example: A = [9, 4, 5, 3], the output is 2.
Because A has inversion pairs: (9, 4), (9, 3).
K’s Largest Number
Output the k’s largest number of the input sequence
For example: A = [179, 208, 306, 93, 859, 984, 55, 9, 271, 33], K = 2, the output is: 859
You are allowed to use STL.
But don’t use any STL related to sort.
There are multiple test cases, and each test case begins with a line containing two integers n and op, the number of elements in sequence and the option.
The next line includes the n integers in the sequence.
Please note:
1. 1 <= the number of elements <= 1000000
2. 1 <= option <= number of elements
3. 1 <= value of each element <= 2^30 - 1
(each value is decimal integer)
There won’t be a new line at the end of the file.
The k’s largest element / QQ inversion pair count according to option
Each output should followed by a new line