Блог пользователя Jack_sparrow_06

NEED OPTIMAL SOLUTION
Автор Jack_sparrow_06, история, 17 месяцев назад, По-английски

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;

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
17 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
17 месяцев назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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})$$$.

→ Ответить
»
17 месяцев назад, # |
← Rev. 2   Проголосовать: нравится +15 Проголосовать: не нравится

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

→ Ответить
»
17 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
17 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
17 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить