Алгоритм Мо позволяет отвечать на запросы на отрезках неизменяемого массива в оффлайн (то есть сперва узнать все запросы и только потом ответить на них).
Преимущество алгоритма Мо по сравнению с другими подходами заключается в том, что он зачастую позволяет считать сложные запрашиваемые функции, которые зачастую непонятно как поддерживать в дереве отрезков или других структурах данных. При этом сам алгоритм довольно прост в реализации.
Минус же заключается в том, что, скорее всего, будет существовать асимптотически более эффективный по времени способ, например с помощью персистентного дерева отрезков, однако реальный выигрыш по времени, вероятно, не окупит затраты на написание более сложного кода.
Саму асимптотику алгоритма Мо обозначим позже.
Опишем сам алгоритм:
Условно (то есть не выполняя это фактически) разобьем имеющийся массив на блоки по S элементов. То есть первый блок с элементами с индексами [0;S-1], второй блок с элементами с индексами [S; 2S-1] и т.д. Последний блок, скорее всего, будет содержать меньше чем S элементов, но это не страшно.
Далее отсортируем имеющиеся запросы следующим образом: сперва по возрастанию номера блока, в котором находится левая граница запроса, а при их равенстве по возрастанию правой границы запроса.
Теперь будем обрабатывать запросы в этом порядке, лениво передвигая границы от текущего запроса к следующему.
Делается это так:
Изначально как-нибудь посчитаем ответ для первого запроса или можно начать с нейтральных значений, то есть с вырожденного отрезка. Теперь у нас есть какие-то текущие границы, ответ для отрезка в этих границах и, возможно, какой-то аккумулятор, с помощью которого мы считаем значение функции (например, вспомогательный массив с количеством элементов на этом отрезке или т.п.).
Далее будем переходить от текущего отрезка к следующему посредством единичных сдвигов текущих границ.
То есть, если новая правая граница правее, чем текущая, то поэлементно расширяем текущий подотрезок, добавляя новые справа, и пересчитываем функцию и так, пока текущая правая граница не достигнет новой.
Если новая правая граница левее, чем текущая, то поэлементно сужаем текущий подотрезок, удаляя старые справа. Аналогично с левой границей.
Рекомендуется сперва расширять отрезок, а затем сужать, чтобы случайно не получить вырожденный отрезок.
Таким образом, необходимо лишь уметь добавлять/удалять один элемент с конца массива и пересчитывать после этого функцию, что как раз и делает алгоритм Мо пригодным и удобным для подсчета сложных запросов на отрезках.
За сколько это работает?
Давайте выберем S равное sqrt(N), где N - длина массива. Таким образом у нас будет sqrt(N) блоков по sqrt(N) элементов в каждом.
Посчитаем количество перемещений границ:
Если правые границы упорядочены, то указатель на правую границу сделает не больше чем N перемещений. Но при переходе левой границы в следующий блок упорядоченность правых границ обнуляется. Блоков sqrt(N) штук, поэтому всего правая граница сместится \(О(N \cdot \sqrt{N})\) раз.
При каждом переходе к новому запросу левая граница может перемещаться вдоль целого блока, то есть на sqrt(N) элементов. При переходе к новому блоку на любое количество элементов (в некоторых блоках может не быть запросов), но суммарно для всех междублочных переходов не больше чем на N элементов (так как мы упорядочевали запросы по возрастанию блока). Исходя из этого левая граница сместится \(O(M \cdot \sqrt{N} + N)\) раз, где M - число запросов.
Учитывая сортировку запросов, суммарно алгоритм Мо работает за \(O(M \cdot log(M) + (N + M) \cdot \sqrt{N} \cdot f(x))\), где f(x) - время, за которое вы пересчитываете необходимую функцию при добавлении/удалении одного элемента.
Рассмотрим пример применения:
В рамках этой задачи будем рассматривать только целые неотрицательные числа.
Дан массив из n чисел. Необходимо ответить на m запросов нахождения mex-a на подотрезке. Mex (minimum excluded) - операция над множеством чисел, которая возвращает минимальное число, которого нет в этом множестве. Примеры:
mex({0, 1, 2}) = 3.
mex({0, 1, 3}) = 2.
mex({1, 2, 3}) = 0.
mex({}) = 0.
Искать mex массива чисел можно следующим образом: заведем упорядоченное множество (set) чисел, которых нет в нашем массиве. Изначально это все числа от 0 до n+1 (mex множества не превосходит его размера+1). Далее можно поэлементно добавлять числа из массива, удаляя их из множества отсутствующих. Когда добавим все числа, mex будет равен наименьшему число в множестве отсутствующих. Также мы можем обновлять mex при удалении чисел из массива. Для этого нам потребуется дополнительно хранить массив количеств, чтобы понимать когда мы добавили новое, а когда удалили последнее.
Таким образом, мы можем пересчитывать mex множества при добавлении или удалении одного числа, чего достаточно для применения алгоритма Мо. Операция добавления и удаления одного числа занимает \(O(log(n))\) времени, поэтому общая асимптотика будет равна \(O(m \cdot log(m) + (n + m) \cdot \sqrt{n} \cdot log(n))\)
Код представлен ниже:
// структура для запросов
struct query {
// левая граница, правая граница и номер запроса
int l, r, num;
};
// размер блока
// вместо честного sqrt(n) зафиксируем его как константу (320 ~= sqrt(100000))
// так можно будет ее регулировать, что может позволить ускорить программу
const int S = 320;
// компаратор для сортировки запросов
bool cmp(const query& a, const query& b) {
if (a.l / S != b.l / S)
return a.l / S < b.l / S; // сперва сортируем по возрастанию номера блока левой границы
else
return a.r < b.r; // при равенстве сортируем по возрастанию правой границы
}
const int MAXN = (int)1e+5 + 5;
// исходный массив
int arr[MAXN];
// структура для аккумулирования ответа на запросы
struct state {
// границы текущего подотрезка
int l, r;
// множество чисел, которых нет в текущем подотрезке
set absent;
// массив, хранящий количество чисел в текущем подотрезке
int cnt[MAXN];
state() {
// изначально будет вырожденный подотрезок, то есть пустое множество
l = 0;
r = -1;
for (int i = 0; i < MAXN; i++) {
cnt[i] = 0; // в пустом множестве количество всех чисел равно нулю
absent.insert(i); // при этом все числа в нем отсутствуют
}
}
// добавление числа в подотрезок
// увеличиваем количество
// если числа не было, то оно появилось, то есть надо его удалить из множество отсутствующих
void add(int x) {
if (cnt[x] == 0)
absent.erase(x);
cnt[x]++;
}
// удаление числа
// уменьшаем количество
// если оно стало нулевым, то число исчезло, то есть надо его добавить во множество отсутствующих
void remove(int x) {
cnt[x]--;
if (cnt[x] == 0)
absent.insert(x);
}
void add_right() {
r++;
add(arr[r]);
}
void add_left() {
l--;
add(arr[l]);
}
void rem_right() {
remove(arr[r]);
r--;
}
void rem_left() {
remove(arr[l]);
l++;
}
// mex текущего подотрезка = минимальное число во множестве отсутствующих
int get_mex() {
return *absent.begin();
}
};
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
cin >> arr[i];
int m;
cin >> m;
vector q(m);
vector ans(m);
// сперва узнаем все запросы, а лишь потом отвечаем на каждый
for (int i = 0; i < m; i++) {
cin >> q[i].l >> q[i].r;
q[i].l--; q[i].r--;
q[i].num = i; // запоминаем изначальный номер, т.к. после сортировки он поменяется
}
sort(q.begin(), q.end(), cmp);
state s = state();
for (int i = 0; i < m; i++) {
// сперва пытаемся добавлять, чтобы случайно не получить невалидный подотрезок (где левая граница больше правой)
while (s.r < q[i].r)
s.add_right();
while (s.l > q[i].l)
s.add_left();
// потом пытаемся удалять
while (s.r > q[i].r)
s.rem_right();
while (s.l < q[i].l)
s.rem_left();
// когда текущий подотрезок стал равен подотрезку-запросу можем запросить ответ для него
ans[q[i].num] = s.get_mex();
}
for (int i = 0; i < m; i++)
cout << ans[i] << ' ';
return 0;
}
P.S.
Существуют более продвинутые использования алгоритма Мо, но выходящие за рамки этой теории, а именно, использование этого алгоритма при учете запросов на обновление элементов (3-Д алгоритм Мо) и использование его для запросов на деревьях (алгоритом Мо на деревьях).
Также существуют эвристики (неасимптотические оптимизации), связанные с более продвинутым порядком запросов, которые позволяют снизить количество перемещений границ при переходе между запросами. Один из простых способов - при равенстве блока левой границы сортировать правые по возрастанию или по убыванию в зависимости от четности номера блока. Более продвинутый - использовать кривую Гильберта (подробнее
здесь).