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)