Hope someone will be able to give me an idea about this problem :
John has N movie discs placed in a stack, which are numbered 1, 2 ... n from the top. For every time he takes a disc, John will skillfully pull the disc he wants to watch from the stack. And after using it later, he put this plate on top again, messing up the order. Now he has m discs to watch in turn, where on the stack he wants to watch it each time he watches the ith disc ?
Sample Input
5 3
4 4 5
Sample Output
4 1 5
Note : n, m <= 1e5.
Thank you so much!
Here's the link to problem statement.
One idea to solve this is to use a Fenwick tree which supports point update, range sum queries. You can make it of size n+m, and initially fill the last n spots with 1s representing that there is a disk there. Then, each time you have a query, you can change the position of some element by putting it to the new front, and removing the 1 from its old position, and put a new 1 on the new front of the array.
You'll need one array to store the positions of each disk in the fenwick tree, and a fenwick tree to count how many disks are on top of the one you are about to remove.
gà