MEX Data structure

Revision en1, by kaldiuo, 2018-02-21 12:32:12

There are q<=5*10^5 online queries of 2 types for a set of integers:

  1. Add an integer 1<=x<=10^9 to the set
  2. Find the minimum element >=x that isn't present in the set

Is there a way to efficiently process these queries?

Tags data structures

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English kaldiuo 2018-02-21 12:35:18 35 Tiny change: 'e set\n2. Find the' -> 'e set\n2. Remove an integer from the set\n3. Find the'
en1 English kaldiuo 2018-02-21 12:32:12 248 Initial revision (published)