Hi!
Here goes another video! And now it's in English! This topic is experimental for my channel. I'm talking about everything you need to know about the MEX to solve problems involving this operation. I hope you find this video helpful.
In the future, I'm going to translate my other videos into English. So stay tuned!
You can check out my previous videos on my channel
Contest on mex (and others) is here
Also, there's the Russian version of this video if you speak Russian here
P.S. I'm definitely not fluent in English but I hope you'll understand everything. I see some problems in my English but I'd appreciate it if you said what you found weird in my speech or text.
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.net/group/1rv4rhCsHp/contest/321292
Oh, yeah. I should've added it to this post too.
P.S. Done.