Все, что надо знать про MEX

If you speak English here is the English version of this video:    • Everything you need to know about MEX oper...   Привет! Я Егор. Это видео — новый формат для этого канала. В нем я в очень сжатой форме рассказываю все, что вам надо знать про mex для того, чтобы успешно решать задачи, в которых используется эта тема. Надеюсь, это видео вам покажется полезным. На этом канале я делаю анимированные видео, объясняющие разные алгоритмы и структуры данных. Я затрагиваю как самые базовые темы: префиксные суммы, бинарный поиск, сортировки; так и продвинутые: disjoint sparse table, segment tree beats, heavy-light декомпозиция, link-cut tree, лямбда-оптимизация, FFT и другие. Если вам это интересно, подписывайтесь на канал :) Можете предлагать темы, на которые вы хотели бы увидеть видео, в комментариях к этому видео или лично мне в телеграме. Также можете писать мне, если чего-то не поняли или у вас есть какие-то вопросы. С радостью отвечу! Успехов на контестах! Контест на codeforces:
Статья про дерево отрезков:
Статья про игры на графах и теорию Шпрага-Гранди:
Разбор задачи на 3D алгоритм Мо (задача F):
Хочу выразить огромную благодарность Гранту Сандерсону — автору канала 3blue1brown за вдохновение и за великолепную библиотеку manim, при помощи которой была сделана анимация в этом видео:
   / @3blue1brown   Содержание: 00:00 - Вступление, определение 00:32 - Поиск mex'а множества за O(n) 01:21 - Поиск mex'а меняющегося множества за O(n log n) 03:30 - Только операции добавления 04:03 - Храним mex в дереве отрезков и в боре 05:36 - Самый полезный трюк, о котором никто не знает 05:47 - Нимовые числа в играх на графах 07:36 - Mex на отрезке за O(log n) 09:07 - Mex на отрезке в меняющимся массиве Мои контакты: telegram:
codeforces:
instagram:   / peltorator