Кратко про алгоритм Мо
Рассмотрим задачу 1. Заметим, что её можно решить с помощью персистентных структур данных. Однако, поставим себе цель решить задачу 2. Да и с персистентностью бывают проблемы.
Алгоритм 1
Будем решать задачу offline. Отсортируем запросы по <$$$\frac{l}{k}$$$, r>, где k — некоторое число. Очевидно, что мы можем легко добавить/удалить одно число (для этого можно поддерживать отдельный массив B, что $$$B_{i}$$$ = количеству учтённых вхождений числа i). Разобьем запросы на блоки с одинаковым $$$\frac{l}{k}$$$. Очевидно, что таких блоков $$$O(\frac{n}{k})$$$. Пусть сейчас насчитан ответ для отрезка [L; R]. Будем обновлять ответ, сдвигая левую и правую границу, пока они не станут равны границам текущего запроса. Заметим, что для каждого блока левая граница пройдет $$$O(k)$$$ шагов для каждого запроса блока, а правая — $$$O(n)$$$, так как правая граница запросов в блоке неубывает. Тогда всего левая граница пройдет $$$O(q \cdot k)$$$ шагов, а правая — $$$O(\frac{n^2}{k})$$$. Приняв n = q, k = $$$\sqrt{n}$$$ получаем асимптотику $$$O((n + q)\cdot\sqrt{n})$$$.
У этого варианта алгоритма есть есть две проблемы. Во-первых, он достаточно медленный.
Подумайте над второй проблемой сами.
Алгоритм 2
Отсортируем запросы таким же образом, как и в первом алгоритме.
Назовём блоком запросы с одинаковым $$$\frac{l}{k}$$$. Заметим, что блоков $$$O(k)$$$. Обработаем запросы длины $$$\leq$$$ k отдельно. Теперь в каждом блоке длина запросы $$$\geq$$$ k, значит, в него входит позиция $$$k \cdot (\lfloor \frac{l}{k} \rfloor + 1)$$$. Для каждого такого блока сохраним указатель на максимальную правую границу R, которую мы обработали для текущего блока (изначально R = $$$k \cdot (\lfloor \frac{l}{k} \rfloor + 1)$$$). Пусть текущий запрос (l; r), а максимальная правая граница — R. Тогда добавим элементы R + 1, R + 2, ..., r. Обновим R. Заметим, что не были учтены только элементы l, l + 1, ..., $$$k \cdot (\lfloor \frac{l}{k} \rfloor + 1) - 1$$$. Их $$$O(k)$$$. Таким образом, на обработку каждого запроса необходимо $$$O(k)$$$ времени, а на обработку блока — $$$O(n)$$$. Так как всего блоков $$$O(\frac{n}{k})$$$, итоговая асимптотика — $$$O(\frac{n^{2}}{k} + q \cdot k)$$$. При k = $$$\sqrt n$$$, итоговая асимптотика составит $$$O((n + q) \sqrt n)$$$.
3D Mo
Настало время научиться решать вторую задачу.
Алгоритм 1.
Заметим, что нам ничего не мешает сделать корневую по запросам одновременно с алгоритмом Мо. Разобьем запросы на блоки размера k. Внутри каждого такого блока запросов запустим алгоритм Мо. Итоговая асимптотика — $$$O(\frac{q}{k} \cdot (k^{2} + \frac{n^{2}}{k}))$$$. При n = k алгоритм имеет асимптотику $$$O(nk + \frac{n^3}{k^{2}})$$$. При $$$k = n^{\frac{2}{3}}$$$ получаем $$$O(n^{\frac{5}{3}})$$$.
Алгоритм 2.
Отсортируем запросы, кроме изменений по <l / k, r / k, i>. Тогда у каждого запроса каждая граница лежит в определенном блоке. Для каждой такой пары блоков научимся отвечать на запросы. Давайте перебирать запросы изменения в хронологическом порядке, то есть переберем для каждой пары блока все запросы изменения, будем двигать указатели как в первом алгоритме. Для этого можно поддерживать указатель на последний обработанный запрос. Тогда асимптотика работы алгоритма — $$$O(\frac{n}{k} \cdot \frac{n}{k} \cdot q + qk)$$$ (так как каждый раз каждый l или r может пройти $$$O(k)$$$ шагов. Пусть n = q. Тогда асимптотика — $$$O(\frac{n^{3}}{k^{2}} + qk)$$$. Взяв $$$k = n^{\frac{2}{3}}$$$ получаем $$$O(n^{\frac{5}{3}})$$$.
Алгоритм 3.
Будем сортировать по <i / k, l / k, r>.
Назовем блоком запросы с одинаковым i / k и l / k. Тогда для такого блока можно перебрать все запросы изменения, которые не были обработаны и актуальны для этого блока. Указатель L сдвинется не более чем на k для каждого запроса, а R — на $$$O(n)$$$ для каждого блока. Итого (n = q) $$$O(\frac{n^{3}}{k^{2}} + nk)$$$. При k = $$$n^{\frac{2}{3}}$$$ получаем асимптотику $$$O(n^{\frac{5}{3}})$$$.
Хочется отметить, что:
Задача про mex на отрезке с изменениями — это задача D с заочного тура Открытой олимпиады 2018-2019 года. Решение жюри там тоже за $$$O(\log^2{n})$$$ с помощью двумерной структуры, несколько похитрее вышеописанной конструкции, деталей уже не помню. Можно скачать архив с материалами и почитать код решения.
Задача про пересечение прямоугольников на пути в дереве решается независимо по каждой осей и требует нахождения максимума из левых концов и минимума из правых, т.е. просто поиска на пути минимального/максимального числа. Что делается, например, за $$$O(\log{n})$$$ простыми двоичными подъемами.
You can find a lot of difficult sqrt problems (and some polylog problems) here prepared by ODT
Well known in CNOI because of ODT lol
I think a better way of thinking about Mo's algorithm that allows you to also optimize it in a lot of cases is to think about inserting a separator each $$$k$$$ positions and "bucketing" the queries depending on the first separator that is inside the query (not surprisingly, the
l/k-th). For each bucket, you sort the queries increasingly byrand do sweep-line. This way, you only need a data structure that should be able to:Sometimes not even that is needed for the problem. Nonetheless, you don't need to explicitly have the option to remove.
This is important in a lot of scenarios, for example the "most frequent element in range" problem, which you can solve in $$$O(Q \sqrt{N} \log{N})$$$ with the "standard" Mo's algorithm but rather trivially in $$$O(Q \sqrt{N})$$$ using this formulation. The only downside is that you have to write extra code to handle small queries (length smaller than $$$k$$$), but usually that is just glue code, as you can use the same data structure for that.