Atcoder Median of Medians Solution

http://tonancos.com/3noa

Tags: Inversion counting, binary search, median, prefix sums

Let's say x is the answer to the problem, you want to know how many intervals have a median below or equal to x. If you find how many
intervals have a median less than or equal to x, even though we don't know if x is the median for sure, the binary search helps choose the
greatest possible x. In the binary search we go up if the result is under the median of the intervals (n*(n+1)/2 divided by 2) and down if it's over
it. The answer is the highest x that's over or equal to the median of the intervals (the n*(n+1)/4 thing above).

Then there's the part where you check each interval to see if the median is below or equal to x. Like in the editorial, put 1's for values greater
than x and -1's for values less than x. Then take the prefix sums of this. Then, when you get the sum of an interval, if it's greater or equal to the
interval's median, the median is over x, else it's under x. Then, instead of computing each interval with brute force, you use inversion counting (count the number of unsorted pairs of numbers). This is because when you get the value for the interval, you want to know if the median is over or equal to x, so you only want to know how many intervals have a negative value.

My solution: http://tonancos.com/3nuN