Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

MEX Data structure

Revision en2, by kaldiuo, 2018-02-21 12:35:18

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. Remove an integer from the set
  3. 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)