Модуль: Алгоритм Мо


Задача

1 /4


Количество различных на отрезке

Теория Нажмите, чтобы прочитать/скрыть

Алгоритм Мо позволяет отвечать на запросы на отрезках неизменяемого массива в оффлайн (то есть сперва узнать все запросы и только потом ответить на них).

Преимущество алгоритма Мо по сравнению с другими подходами заключается в том, что он зачастую позволяет считать сложные запрашиваемые функции, которые зачастую непонятно как поддерживать в дереве отрезков или других структурах данных. При этом сам алгоритм довольно прост в реализации. 
Минус же заключается в том, что, скорее всего, будет существовать асимптотически более эффективный по времени способ, например с помощью персистентного дерева отрезков, однако реальный выигрыш по времени, вероятно, не окупит затраты на написание более сложного кода. 
Саму асимптотику алгоритма Мо обозначим позже.

Опишем сам алгоритм:

Условно (то есть не выполняя это фактически) разобьем имеющийся массив на блоки по 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-Д алгоритм Мо) и использование его для запросов на деревьях (алгоритом Мо на деревьях).

Также существуют эвристики (неасимптотические оптимизации), связанные с более продвинутым порядком запросов, которые позволяют снизить количество перемещений границ при переходе между запросами. Один из простых способов - при равенстве блока левой границы сортировать правые по возрастанию или по убыванию в зависимости от четности номера блока. Более продвинутый - использовать кривую Гильберта (подробнее здесь).

Задача

Вам дан массив целых чисел А длиной n.
Необходимо ответить на m запросов вида "сообщите количество различных чисел подотрезка массива А от элемента с индексом l до элемента с индексом r" (обе границы подотрезка включены, массив нумеруется с единицы).

Входные данные:
В первой строке дано два числа: n - количество элементов массива и m - количество запросов (1 <= n, m <= 105).
Во второй строке дано n целых чисел Ai - элементы массива (0 <= Ai <= 106).
Далее дано m строк, в каждой по два числа l и r - границы подотрезка для каждого запроса (1 <= l <= r <= n).

Выходные данные:
В единственной строке выведите через пробел m чисел - для каждого запроса количестве различных чисел на соответствующем подотрезке.

Пример:
 
Входные данные Выходные данные
7 5
1 3 1 2 2 4 1
1 3
4 5
3 7
2 4
7 7
2 1 3 3 1



time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w6421
Комментарий учителя