Hi everyone, Could you please suggest some techniques and how to apply them to solve this problem?
We are given an initially empty array a and q queries of the form id x. Each query id x means inserting element x at position id in array a (it is guaranteed that id <= size(a) + 1). It is also guaranteed that q <= 10^5. The output is to print the array a after q queries
What is the output?
Sorry, the output is to print the array a after q queries
A balanced BST would probably be easiest to implement and most efficient.
You can find the insertion point with ID by keeping track of subtree sizes.
Then you can insert and update sizes as you go up.
At the end you can do an in-order traversal to get the array.
We can solve this problem using offline query trick + fenwick tree. We can try to solve this problem backwards and determine the actual position in the array. Initially, we set all the positions to 1 (occupied) in the array. We can do binary search to find the minimum position idx such that query(1, idx) == id. After doing so, it is guaranteed that idx is the actual position in the final array. Therefore, set ans[idx] = val and set idx to 0 in the fenwick tree (unoccupied).
what about Treap algorithm?