Кратко про алгоритм Мо
Задача 1Количество различных элементов на отрезке
Дан массив A длины n и q запросов.
Запросы:
- Найти количество различных элементов на отрезке [l; r] массива A.
Задача 2Количество различных элементов на отрезке с изменением
Дан массив A длины n и q запросов.
Необходимо уметь:
Рассмотрим задачу 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})$$$.
Немного кода#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> a, cnt;
int ans = 0;
inline void add(int i) {
++cnt[a[i]];
if (cnt[a[i]] == 1) { // cnt[a[i]] == 1 <=> we have not met it before.
++ans;
}
}
inline void del(int i) {
--cnt[a[i]];
if (cnt[a[i]] == 0) { // cnt[a[i]] == 0 <=> there are no integers = a[i] left.
--ans;
}
}
struct query {
int l, r, i;
query() {}
query(int l, int r, int i): l(l), r(r), i(i) {}
};
inline bool cmp(query &a, query &b) {
if (a.l / k == b.l / k) {
return a.r < b.r;
}
return a.l < b.l; // <=> a.l / k < b.l / k
}
int main() {
int n, q;
cin >> n >> q;
a.resize(n);
cnt.assign(1000000, 0);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
vector<query> qq;
int i = 0;
while (q--) {
int l, r;
cin >> l >> r;
qq.push_back(query(l - 1, r - 1, i++));
}
sort(qq.begin(), qq.end(), cmp);
int L = 0, R = -1;
vector<int> answer(qq.size(), 0);
for (query x : qq) {
int l = x.l, r = x.r, i = x.i;
while (R < r) {
add(++R);
}
while (L > l) {
add(--L);
}
while (R > r) {
del(R--);
}
while (L < l) {
del(L++);
}
answer[i] = ans;
}
for(int i : answer) {
cout << i << '\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)$$$.
Еще несколько замечаний В первом алгоритме иногда необходимо писать 4 функции добавления/удаления (add_left, add_right, del_left, del_right).
При использовании второго алгоритма достаточно add_left, add_right, так как вместо удалений можно делать откаты.
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}})$$$.
ПсевдокодВоспользуемся первым алгоритмом Мо.
L = 0, R = -1
for block_of_queries in blocks:
for ask_query in block:
while(L > ask_query.l) add(--L)
while(R < ask_query.r) add(++R)
while(L < ask_query.l) del(L++)
while(R > ask_query.r) del(R--)
changes = []
for change_query in block:
if (has_influence(ask_query, change_query)):
del(change_query.i)
changes.append([array[change_query.i], change_query.i])
array[change_query.i] = change_query.val
add(chenge_query.i)
ans[ask_query].i = global_answer
reverse(changes)
for change in changes:
del(change.i)
array[changes.i] = change.val
add(change.i)
Алгоритм 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}})$$$.
Псевдокодfor left_bucket:
for right_bucket:
last_unused = 0
L = 0, R = -1
array = input_array
for query with l in left_bucket && r in right_bucket:
move L
move R
while last_unused <= query.i:
if (L <= change[last_unused].idx <= R):
delete(change[last_unused].idx)
array[change[last_unused].idx] = change[last_unused].val
add(change[last_unused.idx])
else:
array[change[last_unused].idx] = change[last_unused].val
++last_unused
ans[query.i] = answer
Алгоритм 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}})$$$.
Еще несколько задач.
Задача 1Дан массив.
Необходимо:
Изменять элемент в точке.
Найти mex на отрезке (наименьшее целое неотрицательное число, которое не встречается на этом отрезке).
$$$O(n^{\frac{5}{3}})$$$
Задача 2Дан массив.
Необходимо:
Изменять элемент в точке.
Найти mex {$$$c_{1}, c_{2}, ..., c_{10^{5}}$$$}, где $$$c_{i}$$$ — количество элементов, которые равны i (mex — наименьшее целое неотрицательное число, которое не в данном множестве).
$$$O(n^{\frac{5}{3}})$$$
Задача 3Дан массив.
Необходимо:
$$$O(n^{\frac{5}{3}} + q \ log_{2} \ mod)$$$
Задача 4Дано дерево, в каждой вершине которого написано 4 числа — левый нижний и правый верхний угол прямоугольника.
Необходимо:
- Находить пересечение прямоугольников в вершинах на пути из u в v.
$$$O(n \sqrt n)$$$
Задача 5Дано дерево с числами на ребрах.
Необходимо:
- Находить mex чисел, написанных на ребрах пути из u в v в дереве.
$$$O(n \sqrt n)$$$
Задача 6Дано дерево с числами на ребрах
Необходимо:
$$$O(n^{\frac{5}{3}})$$$
Задача 7Дано дерево с числами в вершинах.
Необходимо:
Изменять число в вершине.
Находить количество делителей числа, которое равно произведению чисел в вершинах на пути из u в v (по модулю $$$10^{9} + 7$$$).
$$$O(n^{\frac{5}{3}} + q \ log_{2} \ mod)$$$
Хочется отметить, что:
Задача про 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 byr
and 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.