Jack_sparrow_06's blog

NEED OPTIMAL SOLUTION
By Jack_sparrow_06, history, 17 months ago, In English

Today's test I was asked to a question and I wrote brute force solution but it gave me an TLE. I want to know the optimal approach for the question. Given an Array of size N, you will be given an integer Q, which represents the no.of.queries will be given. Each query will contain two integer {L, R} where L and R represent the range of integers in the Array. You need to find the median for each query in the given range {L, R}. CONSTRAINTS: 1 <= N <= 1e5; 1 <= Q <= 1e5; 1 <= L <= R <= N;

  • Vote: I like it
  • +6
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Merge tree + bin search, log^3 (awful).

→ Reply
»
17 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

You could use Mo's algorithm combined with using two ordered multisets to track the left half and right half of your items in the active range.for time complexity $$$O(n\sqrt{n}\log{n})$$$.

→ Reply
»
17 months ago, # |
← Rev. 2   Vote: I like it +15 Vote: I do not like it

Can be done by using persistent segment tree in $$$O(Q\log n)$$$

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the your help. Could you give the reference link for the ease of understanding?

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

You only need to use the vjudgian algorithm and open a black hole

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can be done in O(N log N) preprocessing and query using a Trie of decimal digits as string and store index of inserted values in each node in increasing order.

Then, for [L, R] query we find the Kth smallest element (K = (R — L + 1) / 2 for median), in trie using this https://codeforces.me/blog/entry/104650

but to simulate a trie with only elements in [L, R], we binary search the count of indexes in [L, R] while traversing a node, which acts as frequency of that node and then we use Kth smallest in trie technique as mentioned in linked blog.

→ Reply