Hi everyone,
Can someone help me with this problem.
The problem is, initially you are given an empty array A. You are given with 2 types of queries.
The first one is 1 X Y. Which means add X to the array Y times.
The second one is 2 N. Output the number at the Nth position in the array, when the array is sorted increasingly.
For example:
1 5 5
2 4
1 3 6
2 6
2 7
Array after 1st query : 5 5 5 5 5
Array after 3rd quer : 3 3 3 3 3 3 5 5 5 5 5
Then output would be: 5, 3, 5.
What are the limitations?
I don't think you can solve this using exclusively binary search (binary search only helps with searching, here the second query; inserts are still linear time). You would need to use a tree structure to do both operations in logarithmic time. If you want to implement it yourself, you can do it using a modified Fenwick tree, computing the sum of the number of occurrences of each element; you'll need to add an operation that allows you to search elements by their prefix sum (which is their index). You'll probably also be able to implement something similar using a segment tree.
Thanks a lot.
Yes. I am pretty sure that idea would work. I would answer all queries offline. Use coordinate compression to reduce the upperlimit of A[i]. Then for each query of type 1. we would add Y to fen[x]. This can be done in Log(N). To query the Kth element you could use binary search. I would lower bound the "prefix sums" till we find the number which returns sum >= k. This would be our answer. So type 2. would take Log (N) ^ 2.