you given array of n positive integers, a1,a2,…,an. have answer q queries. each query consists of 2 integers l , k. each query have tell kth element larger or equal l in array when such elements listed according increasing order of indices.
example = 22,44,12,16,14,88,25,49
query 1: l = 3 k = 4 since elements greater 3. list whole array i.e. 22,44,12,16,14,88,25,49. 4th element among these elements 16
query 2: l = 19 k = 5 listed elements 22,44,88,25,49. 5th element among these 49.
what have done: each query iterate on whole array , check kth element larger or equal l. complexity : o(q*n)
what require: o(q*logn) complexity.
constraints : 1<=q<=10^5 1<=n<=10^5 1<=ai<=10^5
one possible way solve task use immutable binary (rb) tree.
first need sort array in ascending order, storing original indices of elements next elements.
traverse array in reverse (descending) order, adding elements 1 one immutable binary tree. key in tree original index of element. tree immutable, adding element mean constructing new tree added element. save tree created on each step near corresponding element (the element last added tree).
having these trees constructed each element can queries in o(log n) time.
query: first, perform binary search l in sorted array (o(log n)) element bigger l. you'll find element , corresponding tree of indices of elements bigger l. in tree can find k-th largest index in o(log n) time.
the whole algorithm take o(n log n + q log n) time. don't believe possible better (as sorting original array seems inevitable).
the key of approach using immutable binary tree. structure shares properties of mutable binary tree, such insertion , search in o(log n), while staying immutable. when add element such tree, previous version of tree preserved, nodes different previous "version" of tree recreated. it's o(log n) nodes. creating n trees elements of array require o(n log n) time , o(n log n) space.
you can use immutable rb tree implementation in scala reference.
Comments
Post a Comment