Problem E: Median I

## Problem E: Median I

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 2192  Solved: 258
[Submit][Status][Web Board]

## Description

Given two nondecreasing sequences $$a$$ and $$b$$, and their length are both $$n$$. What's the median of after combining the subarray $$a[l..r]$$ and subarray $$b[l..r]$$ ?

Subarray $$a[l..r]$$ is a sub-array of $$a$$, it includes $$a_l, a_{l+1} ... a_r$$ for $$1≤l≤r≤n$$, its length is $$r−l+1$$.

You’d like to determine the median of this set of $$2k(k=r-l+1)$$ values, which we will define here to be the $$k$$-th smallest value. For example: median([1,2,3,4])=2.

## Input

The 1st line contains two positive integers $$n(1⩽ n ⩽ 100000)$$  and $$T(1⩽ T ⩽ 100000)$$ which is the number of testcase.

The 2nd line contains $$n$$ integers: $$a_1, a_2 ... a_n$$. For each $$a_i(0⩽ a_i ⩽ 10^9)$$

The 3rd line contains $$n$$ integers: $$b_1, b_2 ... b_n$$. For each $$b_i(0⩽ b_i ⩽ 10^9)$$

Then $$T$$ lines follow. Each line contains two integers $$l$$ and  $$r(1⩽ l ⩽ r ⩽ n)$$ for a test case.

## Output

Output $$T$$ lines. Each line contains an integer $$ans$$, the median of  after combining the  subarray $$a[l..r]$$  and subarray $$b[l..r]$$ .

## Sample Input

5 2
1 3 5 7 9
2 3 4 5 6
5 5
1 5

## Sample Output

6
4

## HINT

The correspond solutions to the sample is :

(1)$$a_5$$=9, $$b_5$$=6, after combining is [9 6], the median is 6.

(2)Combine $$a$$ and $$b$$  then sort it can get [1 2 3 3 4 5 5 6 7 9], the median is 4.

[Submit][Status]