## Editorial for DMOPC '19 Contest 2 P3 - Selection

**only**when stuck, and

**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.

**Submitting an official solution before solving the problem yourself is a bannable offence.**

Author:

For subtask 1, a simple brute force algorithm will suffice. For each query, we can sort the subarray, take the th best item, and then revert the array to its original state.

**Time complexity: **

For subtask 2, we can build a Binary Indexed Tree (BIT) over our array and update it accordingly. For each query, we use our BIT to find the number of `1`

s in our subarray. If this is more than , then the th best item has goodness `1`

. Otherwise, it has goodness `0`

.

**Time complexity: **

For subtask 3, we instead build a BIT for the number of elements for each possible . Similar to subtask , we can use our BIT's to find for each possible , the number of elements that have as its goodness. The th best item is thus the highest possible such that the number of elements with a value greater than or equal to is more than , which can be checked with our BITs.

**Time complexity: **

## Comments

For the third subtask, how do the queries process the range l, r? It seems like the BIT does not track the range.

edit: figured it out, ignore pls

A segment tree for number frequency would suffice as well. O(20mlog(n))

"26 pbds" - ChrisT