Good time of a day, Codeforces community :)
I actually was a little bit uncertain if I have the right (well not right but if my question is eligible for asking) to ask help in this problem. The tag on the problem says that it can be solved with Segment/Interval Tree but I tackled the problem and was unable to solve it. I had some ideas of solutions that used the Linked List, but well, you know it was too slow :) I browsed the web for the solution but was unable to find it. Finally, I found the bravery and am asking the help from you :) The task is HERE.
I am very grateful to anyone that found the time to read this.
Thank you very much in advance! :)
I got Accepted using Binary Indexed Tree (BIT). The main idea is quite straightforward: first, performing all removing operations to obtain lucky numbers sequence A, then for each query n find the n-th number on A.
The sample test gives us a hint: the largest element on A in the end is M = 1429431. So we simply create a BIT for range [1,1429431], and use binary search to find the value in the "new" index in log(M)^2.