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

If you speak English here is the English version of this video:    • Everything you need to know about MEX...  

Привет! Я Егор. Это видео — новый формат для этого канала. В нем я в очень сжатой форме рассказываю все, что вам надо знать про mex для того, чтобы успешно решать задачи, в которых используется эта тема. Надеюсь, это видео вам покажется полезным. На этом канале я делаю анимированные видео, объясняющие разные алгоритмы и структуры данных. Я затрагиваю как самые базовые темы: префиксные суммы, бинарный поиск, сортировки; так и продвинутые: disjoint sparse table, segment tree beats, heavy-light декомпозиция, link-cut tree, лямбда-оптимизация, FFT и другие. Если вам это интересно, подписывайтесь на канал :) Можете предлагать темы, на которые вы хотели бы увидеть видео, в комментариях к этому видео или лично мне в телеграме. Также можете писать мне, если чего-то не поняли или у вас есть какие-то вопросы. С радостью отвечу! Успехов на контестах!

Контест на codeforces: https://codeforces.com/group/1rv4rhCs...

Статья про дерево отрезков: https://e-maxx.ru/algo/segment_tree

Статья про игры на графах и теорию Шпрага-Гранди: https://e-maxx.ru/algo/sprague_grundy

Разбор задачи на 3D алгоритм Мо (задача F): https://codeforces.com/blog/entry/58033

Хочу выразить огромную благодарность Гранту Сандерсону — автору канала 3blue1brown за вдохновение и за великолепную библиотеку manim, при помощи которой была сделана анимация в этом видео:

https://github.com/3b1b/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:

https://t.me/peltorator

codeforces:

https://codeforces.com/profile/peltor...

instagram:

  / peltorator