\(MEX\) множества является минимальное неотрицательное целое число, отсутствующее в множестве.
Основным достаточно простым, но не совсем очевидным свойством является тот факт, что \(MEX\) для какого-то множества \(S\) не превосходит размера множества. Иными словами \(MEX \le |S|\). Это следует из факта о том, что если \(MEX(S) = k\), то в \(S\) присутствует \(0, 1, 2...k-1\).
Рассмотрим простую задачу: найти \(MEX\) множества. Благодаря предыдущему свойству, мы можем создать массив \(exist\) размером \(n+1\), где в \(exist[i]\) хранится \(1\) или \(0\) - есть ли \(i\) в множестве. \(MEX\) множества - минимальное \(i\), где \(exist[i]\) равно 0.
При необходимости поддерживать \(MEX\) множества с запросами удаления/добавления элементов, можно в какой-нибудь структуре данных, поддерживающих удаление/добавление/запрос минимума не более чем за \( \log{n}\), хранить все элементы, отсутствующие в множестве. Опять же, их не больше количества запросов. При запросе \(MEX\) выдавать минимальный элемент в структуре.
Также можно поддерживать ДО по массиву \(exist\), и спуском по ДО находить первое \(exist[i]=0\).
Кроме того, удобно поддерживать \(MEX\) с помощью std::bitset: изменение \(exist\) за \(O(1)\) и нахождение первого нулевого элемента с помощью find_first() за \( \frac{n}{64} \)
Если использовать корневую декомпозицию и битсет, то ускорение будет значительным.
MEX можно также находить с помощью двоичного бора, также спускаясь в нужную вершину. Кроме того, можно еще поддерживать запросы вида "для каждого \(a[i]:= a[i]\space xor\space x\)". В таком случае просто меняем местами ветки в тех битах, где в \(x\) стоит единица.
Пускай дан массив и надо отвечать на запросы MEX на отрезке. В оффлайн можно использовать алгоритм Мо, а также ДО + сканлайн - построим массив \(last\), где \(last_i\) - последнее вхождение \(i\) в массиве (проинициализируем \(-1\)), построим ДО на минимум. Будем обрабатывать массив слева направо, присваивая \(last[ a_i ] = i\). Когда мы обработали \(r\) чисел, можем ответить на запрос \([l;r]\) - производим спуск по ДО: если значение в левом сыне меньше \(l\) - спускаемся в него, иначе идем в правого сына. Сделаем ДО персистентным и сможем обрабатывать запросы в онлайн.
Но в частности мы умеем отвечать на запросы на перестановке: предподсчитаем MEX на префиксах и суффиксах. Тогда ответом на запрос \( [l;r] \) равен \( min(pref[r],suf[l]) \)
Докажем это. Пускай ответ на запрос равен \(x\). Тогда ответ по формуле точно не меньше, потому что ответы на префиксе и суффиксе не меньше. Кроме того, ответ по формуле не больше, так как если на префиксе или суффиксе ответ больше \(x\), значит на нем присутствует число \(x\), которое не будет присутствовать на другой части массива, т.к. это перестановка.