Hello! I've tried to come up with the solution for next problem but I can't. Please help! Problem: we have an array used, in the beginning used[i]=false for all i. And we are given queries: an index i. We should find the smallest index k of array such that used[k]=false and k>=i. For each query we should find this k and after each query do used[i]=true. Thanks for help!
This should have several simple solutions, but one is to use disjoint-set union to keep intervals of indices such that used[i]=true, and for each set store its maximum element. This allows you to answer queries in O(α(n)) time.
Make a set which contains all indices of non-used elements.
Query 1. Find lower_bound(i) and delete it from set. O(log n)
Query 2. Add i to our set. O(log n)