Initially, I have given empty list. I have given Q queries, each queries can perform two types of operation on this list as :
1 x y : Insert value x, y times in list.
2 k : Print kth element of sorted list.
Constraints:
1<= Q <= 2*100000
1<= x,y <= 10^9
At any query, k is always less than or equal to list size.
List can have maximum 10^5 different values.
I have tried to solve this using set of pairs, but for each print it takes O(n) time in worst case.
Please, helps in figure out to solve these operation in O(n*log n ) where n stands for maximum size of list.
Hello, you can solve it with Fenwick Tree. The first thing to do is do coordinate compression on x (So the algorithm works offline). For query 1: You should add y in the position of x (new value of x after coordinate compression). For query 2: You can do binary search to find the first index where the sum from 0, to that index, is >= k. For that, you can use binary search normally and query in Fenwick tree in O(logn) which leads to find the answer in O((logn)^2). Or you can use the trick of binary search on Fenwick tree. Here is the code of that trick and do it in O(logn). The total complexity is O(q*logn)
Deleted
If you can do it off-line, then you can first re-assign 1 — 105 to all x while preserving their relative order (e.g. {3, 2, 5, 2} => {2, 1, 3, 2}). After that you can use data structure like Binary Index Tree to maintain the prefix sum of count of each number, then each insert query can be done in O(logN). Queries are equivalent to finding the first prefix sum of count greater than or equal to k, this can also be done in O(logN) on the Binary Index Tree. (I think this blog by someone else may help you.)
If you must do it on-line, then you need to use something like Treap to dynamically maintain both the order and prefix-sum of count.
Sorry for my poor english :)
I know the question has already been answered but it may help someone to know that there is an alternative to Treaps in solving the problem on-line.
If you have a way with pointers you can do it with a binary indexed tree or a segment tree, the catch is that instead of creating all the elements you only create the ones that you need (at each update you create at most log2(10^9) new elements).
Time complexity O(q * log2(q)) Space complexity O(q * log2(q))
What do you mean by 'the ones you need' and why would that only be
log2(10^9)?One way of maintaining "only the nodes" you need is with a implicit/dynamic segment tree. See https://codeforces.com/blog/entry/19080?#comment-239938 for an explanation. At most log_2(10^9) nodes are created during each insertion.
but what if we are inserting and deleting elements fenwick tree won't work like that or would it? as I've seen the size should be constant
Let's create Treap which leafs contains pairs (x, y) (x — number, y — count). And we need updating the function root->f = root->left->f + root->right->f + root->y. If we answering on first query, we need search x element in Treap (or add him if Treap dont't contains x), add y value, and update function f. Consider second query. If we stay in some vertex we can go down to left son or right son. If root->left->f < k <= root->left->f + root->y return root->x. If root->left->f >= k go down to left son and if k > root->left->f + root->y go down to right son. Complexity O(log n) time per query and O(n) memory.