Median queries

★★★★★

1.9

15 votes

Advanced Algorithms, Algorithms, Approved, Easy, Grammar-Verified, Recruit, Square Root Decomposition

Details

Submissions

Discussion

Editorial

Problem

You are given an array A consisting of N elements.

For a subarray of A of length $len$ , you have to sort the elements of the subarray in a non-decreasing order. The element at the position $ceil({len \over 2})$ is called the median of the subarray. Consider the array and each subarray to be 1 indexed

Write a program to answer Q queries of the following types:

You are given two integers L and R.
You have to find the median of a subarray $A_L, A_{L+1}, \ldots, A_R$ of the array A.

Input format

First line: N
Second line: N space-separated integers (denoting the array A)
Third line: Q
Next Q lines : Two space-separated integers L and R

Output format

For each query, print the median of the subarray.

Constraints

$1 \le N, Q \le 5 \times 10^4$
$1 \le A_i \le 10^9$
$1 \le L \le R \le N$

Time Limit: 4

Memory Limit: 512

Source Limit:

Explanation

In the 1-st query subarray is ${2, 4, 5, 3, 1, 6}$ . After sorting it will be ${1, 2, 3, 4, 5, 6}$ . The median is 3.

In the 2-nd query subarray is ${4, 5, 3}$ . After sorting it will be ${3, 4, 5}$ . The median is 4.

In the 3-rd query subarray is 5. It's already sorted, so we can easily say that he median is 5.