Алгоритм Мо: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
 
(не показано 7 промежуточных версий этого же участника)
Строка 3: Строка 3:
:* [http://www.spoj.com/problems/DQUERY/ Количество различных элементов на отрезке]
:* [http://www.spoj.com/problems/DQUERY/ Количество различных элементов на отрезке]
:* Наиболее частый элемент на отрезке
:* Наиболее частый элемент на отрезке
:* Количество инверсий на отрезке
:* [http://codeforces.com/contest/220/problem/B Количество чисел x, встречающихся x раз на отрезке]
:* [http://codeforces.com/problemset/problem/220/B Количество чисел x, встречающихся x раз на отрезке]
:* [http://www.codechef.com/problems/IITI15 Количество инверсий на отрезке]
* Элементы массива не меняются;
* Элементы массива не меняются;
* Ответ на запросы в оффлайне (запросы будут сортироваться, отвечать будем не в том порядке, в котором они даны).
* Ответ на запросы в оффлайне (запросы будут сортироваться, отвечать будем не в том порядке, в котором они даны).
Строка 51: Строка 51:
     ans[queries[i].index] = curAns;
     ans[queries[i].index] = curAns;
  }
  }
Обрати внимание: в некоторых задачах важен порядок операций: например, сначала расширяем рабочий отрезок, затем сужаем.


== За сколько это работает ==
== За сколько это работает ==
Строка 65: Строка 66:
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9C%D0%BE neerc.ifmo.ru/wiki — Алгоритм Мо]
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9C%D0%BE neerc.ifmo.ru/wiki — Алгоритм Мо]
* [http://ipc.susu.ru/575.html ipc.susu.ru — Алгоритм Мо]
* [http://ipc.susu.ru/575.html ipc.susu.ru — Алгоритм Мо]
* [http://wiki.algocode.ru/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9C%D0%BE algocode.ru — Алгоритм Мо]
* [http://blog.anudeep2011.com/mos-algorithm/ blog.anudeep2011.com — Mo's algorithm]
* [http://blog.anudeep2011.com/mos-algorithm/ blog.anudeep2011.com — Mo's algorithm]
* [http://www.hackerearth.com/ru/practice/notes/mos-algorithm/ hackerearth.com — Mo's algorithm]
* [http://www.hackerearth.com/ru/practice/notes/mos-algorithm/ hackerearth.com — Mo's algorithm]
* [http://www.hackerrank.com/topics/mos-algorithm hackerrank.com — Mo's algorithm]
* [http://www.hackerrank.com/topics/mos-algorithm hackerrank.com — Mo's algorithm]
* [http://codeforces.com/blog/entry/72690 Codeforces — Mo's Algorithm (with and without update)]
* [https://codeforces.com/blog/entry/81716 Codeforces — Everything on Mo's Algorithm]
* [https://codeforces.com/blog/entry/83630 Codeforces — Два варианта написания алгоритма Мо и 3Д Мо]
Задачи:
* [http://codeforces.com/contest/86/problem/D Codeforces 86.D]
* [http://codeforces.com/contest/220/problem/B Codeforces 220.B]
* [http://www.spoj.com/problems/DQUERY SPOJ DQUERY]
* [http://www.codechef.com/problems/IITI1 CodeChef IITI1] (понадобится дерамида или сжатие координат + дерево Фенвика)

Текущая версия от 20:20, 29 июня 2021

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

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

Что делаем

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

struct Query {
    int left, right, block, index;
} queries[100010];

int blockSize = sqrt(arraySize); 
for (int i = 0; i < queriesCount; i++) {
    scanf("%d%d", &queries[i].left, &queries[i].right);
    queries[i].block = queries[i].left / blockSize;
    queries[i].index = i;
}

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

bool compare(Query &a, Query &b) {
    return tie(a.block, a.right) < tie(b.block, b.right);
}

sort(queries, queries + queriesCount, compare);

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

int l = 0, r = 0, curAns = ... /* ответ для [0..0] */;

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

for (int i = 0; i < queriesCount; i++) {
    while (l < queries[i].left) {
        ... /* исключаем a[l], обновляем curAns */
        l++;
    }
    while (l > queries[i].left) {
        l--;
        ... /* добавляем a[l], обновляем curAns */
    }
    while (r < queries[i].right) {
        r++;
        ... /* добавляем a[r], обновляем curAns */
    }
    while (r > queries[i].right) {            
        ... /* исключаем a[r], обновляем curAns */
        r--;
    }
    ans[queries[i].index] = curAns;
}

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

За сколько это работает

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

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

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

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

Ссылки

Теория:

Задачи: