Set за O(1) на вставку и корень на взятие минимума

Обычный std::set умеет выполнять операции:

на других его возможностях пока останавливаться не будем. Все эти операции set делает за O($\log_2{n}$), Так что если к set поступит:

- то он отрабоает за $O((q_1 + q_2) \cdot \log_2{n})$

- А что если $q_1$ сильно больше $q_2$, например $q_1 = \sqrt{n} \cdot q_2$, можно ли чем-то заменить set, чтобы он работал быстрее?

Для начала будем считать, что для для всех запросов insert(x) $x \le N$ для некоторого $N$. Потом подумаем, что делать с большими числами

Давайте воспользуемся классической корневой декомпозицией:

заведем массив $cnt[N]$, в котором в индексе $i$ будет количество чисел, равных i в нашем "$set$" (если нам нужен именно set, а не multiset, то $cnt[i] = 0/1$)
разделим этот массив на блоки длины $C$, и для каждого блока сохраним сумму $cnt[i]$ в этом блоке
при операциях insert / erase поддерживать массив $cnt$ и суммы в блоках за $O(1)$ очень просто - просто +-1 в соответствующих ячейках
Чтобы ответить на запрос get_min, пройдем по блокам, пока не найдем такой, что сумма в нем $\neq$ 0, а по нему пройдемся честно. Это сработает за $O(\sqrt{N})$

- итого на те же самые $q_1$ запросов insert/erase и $q_2$ запросов get_min мы ответим за $O(q_1 + q_2 \cdot \sqrt{N})$

- чтобы решить проблему с тем, что числа, добавленные в set могут быть слишком большими, можем воспользоваться алгоритмом сжатие координат

- Заметим, что такой "set" легко обобщается на более сложные, чем get_min, операции, например можно сделать $k$-й минимум без изменения асимптотики

- Эта идея бывает очень полезна при реализации Алгоритм Мо, так как там запростов изменения примерно в $\sqrt{n}$ раз больше, чем запросов оперции

Автор конспекта: Евтеев Тихон

По всем вопросам пишите в telegram @tikhon282