difask's blog

Help! How to solve?
By difask, 9 years ago, In English

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!

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

→ Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

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)

→ Reply