Алгоритм Мо

Когда применяется

• Тяжёлые запросы на отрезках:

• Количество различных элементов на отрезке
• Наиболее частый элемент на отрезке
• Количество чисел x, встречающихся x раз на отрезке
• Количество инверсий на отрезке

• Элементы массива не меняются;
• Ответ на запросы в оффлайне (запросы будут сортироваться, отвечать будем не в том порядке, в котором они даны).

Что делаем

1. Мысленно делим массив на sqrt(N) блоков длины sqrt(N); для каждого запроса вычисляем номер блока, в который попадает его левый конец:

struct Query {
    int l, r, block, index;
};

int blockSize = sqrt(a.size());
vector<Query> queries(queryCount);
for (int i = 0; i < queryCount; i++) {
    int queryL, queryR;
    cin >> queryL >> queryR;
    
    queries[i] = { queryL, queryR, queryL / blockSize, i });
}

2. Сортируем запросы сначала по возрастанию блока, затем по возрастанию правого конца:

bool operator < (const Query &that) const {
    if (block != that.block)
        return block < that.block;
    return r < that.r;
}

sort(queries.begin(), queries.end());

3. Заводим индексы l и r для начала и конца рабочего отрезка, рассчитываем ответ на рабочем отрезке:

Counter counter;
int l = 0, r = 0;
counter.add(a[l], 1);

4. Обрабатываем запросы в порядке сортировки, втупую двигая l и r куда нужно и обновляя ответ для рабочего отрезка:

vector<int> res(queries.size());
for (auto &[queryL, queryR, block, index] : queries) {
    while (queryL < l)
        counter.add(a[--l], 1);
    while (l < queryL)
        counter.add(a[l++], -1);
    while (queryR < r)
        counter.add(a[r--], -1);
    while (r < queryR)
        counter.add(a[++r], 1);
    res[index] = counter.getRes();
}

Обрати внимание: в некоторых задачах важен порядок операций: например, сначала расширяем рабочий отрезок, затем сужаем.

Сложность

Предполагаем, что ответ обновляется за O(1).

Всего обрабатывается sqrt(N) блоков. Внутри каждого блока:

• l при каждом запросе может сдвигаться влево или вправо, но каждый раз не более чем на sqrt(N). Всего по всем блокам — не более Qsqrt(N) раз (Q — количество запросов);
• r может сдвигаться только вправо, не более N раз для блока. Всего по всем блокам — не более Nsqrt(N) раз.

Итоговая асимптотика (Q + N)sqrt(N) (плюс QlogQ на сортировку запросов).

Ссылки

Теория:

• neerc.ifmo.ru/wiki — Алгоритм Мо
• ipc.susu.ru — Алгоритм Мо
• algocode.ru — Алгоритм Мо
• blog.anudeep2011.com — Mo's algorithm
• hackerearth.com — Mo's algorithm
• hackerrank.com — Mo's algorithm
• Codeforces — Mo's Algorithm (with and without update)
• Codeforces — Everything on Mo's Algorithm
• Codeforces — Два варианта написания алгоритма Мо и 3Д Мо

Задачи:

• Codeforces 86.D
• Codeforces 220.B
• SPOJ DQUERY
• CodeChef IITI1 (понадобится дерамида или сжатие координат + дерево Фенвика)