Problem statement
You are given an array. It's size can be as big as 10^5. You'll also be given a some (<=5000) queries. Each query will ask you about the k-th element of the sorted array between indices a and b. How to solve that?
Naive idea is to sort the query subarray and find the answer. As pointed out in the problem statement, naive algorithm will not work. How about keeping some presorted intervals? Hmm...
Remember the way we did merge sort, we divide each interval, sort each of them and merge them. We can pre-process the sorted intervals that way.
How to use the presorted arrays to answer queries? At each query, it's easy to find the intervals of the merge sort tree which are completely contained in the query. We'll have to find the least x for which the number of elements with value <= x is less than or equal to (actually equal to) x. for fixing the x (log n), for each interval (log n intervals), binary search for each interval (log n). So (log n)^3 for each query. So complexity for answering queries is m (log n)^3. With n log n merge sort, the overall complexity is O(n log n + m (log n)^3).
Code
Mistakes:
1. Mistaking it for k-th smallest element finding at first.
2. Annoying mistake: If an element can't be found in an interval, lo of binary search should be decreased by one.
3. Binary search on negative numbers: (a+b)/2 rounds towards zero (ceiling) instead of floor. A workaround is to binary search on min-value + |min-value| and max-value + |min-value| which converts to to a non-negative binary search.
You are given an array. It's size can be as big as 10^5. You'll also be given a some (<=5000) queries. Each query will ask you about the k-th element of the sorted array between indices a and b. How to solve that?
Naive idea is to sort the query subarray and find the answer. As pointed out in the problem statement, naive algorithm will not work. How about keeping some presorted intervals? Hmm...
Remember the way we did merge sort, we divide each interval, sort each of them and merge them. We can pre-process the sorted intervals that way.
How to use the presorted arrays to answer queries? At each query, it's easy to find the intervals of the merge sort tree which are completely contained in the query. We'll have to find the least x for which the number of elements with value <= x is less than or equal to (actually equal to) x. for fixing the x (log n), for each interval (log n intervals), binary search for each interval (log n). So (log n)^3 for each query. So complexity for answering queries is m (log n)^3. With n log n merge sort, the overall complexity is O(n log n + m (log n)^3).
Code
Mistakes:
1. Mistaking it for k-th smallest element finding at first.
2. Annoying mistake: If an element can't be found in an interval, lo of binary search should be decreased by one.
3. Binary search on negative numbers: (a+b)/2 rounds towards zero (ceiling) instead of floor. A workaround is to binary search on min-value + |min-value| and max-value + |min-value| which converts to to a non-negative binary search.
কোন মন্তব্য নেই:
একটি মন্তব্য পোস্ট করুন