vjvjain0's blog

By vjvjain0, 3 weeks ago, In English,

Hey guys! I was doing a question and got an idea of this interesting question.

You are given an n size array a. The ith element of array a[i] is the frequency of the element. You are given q queries which has inputs left limit l and right limit r. You have to tell the median for the range.

1<=n<=10^6
1<=q<=10^5
1<=l<=n
1<=r<=n

Example:

Input:

5 2
4 7 9 1 2
1 2
3 5

Output:

2
3

Share your approaches in the comments. I don't if this is already a question on some online judge.

 
 
 
 
  • Vote: I like it  
  • -11
  • Vote: I do not like it  

»
3 weeks ago, # |
Rev. 3   Vote: I like it -16 Vote: I do not like it

keep partial sums s[i] = a[1] + a[2] + ... + a[i], now the sum of frequences on range [l, r] is s[r] — s[l — 1]

the median on [l, r] is first position k in [l, r] such that a[l] + a[l + 1] + ... + a[k] is greater than a[l] + a[l + 1] + ... + a[r] / 2 + 1 <=> s[k] — s[l — 1] >= (s[r] — s[l — 1]) / 2 + 1 which can be found with binary search

»
3 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

This is a special case of SPOJ's MKTHNUM problem where k = range length/2. Solution is exactly the same.

»
3 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

you can use persistent segment tree to find the k_th element where k = (r — l + 1) / 2 , and node i of the tree stores a[i].