Привет!
Очередное видео! На на этот раз тема немного экспериментальная. В этом видео я в сжатом формате рассказываю все, что надо знать про операцию MEX для того, чтобы решать задачи, в которых она применяется.
There's also the English version of this video here
Буду рад, если вы посмотрите этот ролик и оставите комментарий со своими впечатлениями, замечаниями, мыслями и идеями насчет новых видео. Также можете написать мне в телеграм, если вы чего-то не поняли в видео или у вас возникли любые вопросы. Буду рад ответить!
Можете зайти на мой канал и посмотреть другие видео, если вы их еще не видели.
Контест с задчами на mex.
P.S. Я уверен, что я что-то упустил, так что буду рад, если вы поделитесь в комментариях своими трюками про MEX.
Русская ссылка https://youtu.be/5iW84xlL0j0 ведёт на предыдущее видео
Спасибо! Поправил.
I love these types of explanations with added visual enhancements on it. Keep adding more videos like this!
Thanks! I will.
Great work!Thanks
Thanks!
I thought the English was good, I could understand everything that you said. I really liked the video. Thanks!
Thank you for your support!
This is top-notch stuff!! Please make more videos like this in English.
I'm gonna translate my old videos to English in the nearest future. Thanks!
Great stuff! Looking forward to more tutorials!
Thank you
In Mo's algorithm with range mex queries and point updates in $$$O(n^{\frac{5}{3}})$$$, how can you make transitions (add an element, remove an element, find mex) work in $$$O(1)$$$? Don't they require $$$O(\log n)$$$ (using a set)?
EDIT: lemelisk pointed out that we can use sqrt decomposition instead of a set.
And also you can check out the pinned comment. There's a $$$O(n \log^2 n)$$$ solution!
Mex always will be $$$\le n$$$, so instead of set we can use fenwick/segment tree built on array $$$0 \ldots n$$$ — add/remove will be point updates and lifting for find mex. This substitution already improves constant factor by a lot.
Further, let's replace this trees by sqrt decomposition built on the same array. Then lifting will become $$$O(\sqrt{n})$$$, but update will be $$$O(1)$$$. Since we make only $$$q$$$ liftings and a lot of updates, it will improve our time to $$$O(n^{5/3} + q \sqrt{n})$$$.
Yeah! You're right! Thanks.
That's great!! One more request : You can add practice problems as well.
EDIT : The link to the contest was already there in the description of the video.
LINK : https://codeforces.me/group/1rv4rhCsHp/contest/321292
Oh, yeah. I should've added it to this post too.
P.S. Done.