Maintain mex with efficient union Do you know of any data structure $S[A]$, that maintains a (finite) set $A \subset \mathbb{Z}_{\geq0}$ of non-negative integers, subject to the following operations:


Given $S[A],$ calculate minimal excludant $\mbox{mex} A = \min \ \mathbb{Z_{\geq 0}} \setminus  A.$
Given two data structures for sets $A$ and $B$, construct a data structure, maintaining the union of the two $S[A \cup B]$.


Disjoint set union comes into mind, but I can't think of a way to make it support mex-es.
Intuitively, the problem I see is that we can have a situation in which both $A$ and $B$ contain many small intervals, and then their union is hard to obtain.

Ideally, both of these should be polylog (on the size of the represented sets). 

How about if the sets are from a bounded universe?
Here are two solutions which (as suggested in the question and comments) assume that all the given sets are disjoint and performs destructive set unions (when we find the union of sets A and B, we remove A and B themselves from the family of sets).

Amortized constant time

We maintain objects for the sets and objects for the elements. The sets know what elements they have, as a concatenable list, so that we can list those elements quickly, but we don't keep pointers from the objects to the sets that contain them (because it would be too slow to update them).

There is at most one special set Z, the one containing zero. Every object knows whether it is part of Z or not (a binary flag). The set Z maintains the value of its mex. For every other set, the mex is zero. So you can compute the mex of a set in constant time, given either the set itself or one of its elements.

To form the union of two sets, if neither one is Z, just concatenate their lists. If one of the two sets is Z, run through its elements setting the flag that says the element is now in Z. Then, while the mex is an element of Z, increment it.

Each element accounts for one increment operation to the mex of Z, so the amortized time per element, merge, or mex request is constant.

Worst-case logarithmic time

For a worst-case rather than amortized (but slower) solution, that also allows for creation of new singleton sets and does not assume that the union of all the sets is a contiguous interval, we use the following data structures:


union-find rather than flags to determine the set that contains any element (even if we just do union-by-rank without path compression, this is worst-case logarithmic per find operation)
a binary search tree of the elements in the union of all the sets
for each element, the smallest non-element between it and its predecessor in the binary search tree (or zero if it has no predecessor)
for each binary search tree node, the smallest non-element listed in its subtree (updated in constant time per tree rotation)
the smallest element of each set
a priority queue of the smallest elements of sets that are not Z.


Then at all times mex(Z) is the minimum of the priority queue value and the smallest non-element. And as before, for sets that are not Z, the mex is zero. Adding a new singleton set, merging two sets, or finding a mex all take logarithmic time with more-or-less obvious updates.