Алгоритм Мо - История изменений

Ctrlalt в 10:51, 23 августа 2026

2026-08-23T10:51:10Z

← Предыдущая версия		Версия от 10:51, 23 августа 2026
Строка 11:		Строка 11:
	1. Мысленно делим массив на sqrt(N) блоков длины sqrt(N); для каждого запроса вычисляем номер блока, в который попадает его левый конец:		1. Мысленно делим массив на sqrt(N) блоков длины sqrt(N); для каждого запроса вычисляем номер блока, в который попадает его левый конец:
	struct Query {		struct Query {
	int ~~left~~, ~~right~~, block, index;		int l, r, block, index;
	} ~~queries[100010]~~;		};

	int blockSize = sqrt(~~arraySize~~);		int blockSize = sqrt(a.size());
	for (int i = 0; i < ~~queriesCount~~; i++) {		vector<Query> queries(queryCount);
	~~scanf("%d%d", &queries[i].left~~, ~~&queries[i].right)~~;		for (int i = 0; i < queryCount; i++) {
	~~queries[i].block = queries[i].left / blockSize~~;		int queryL, queryR;
	queries[i]~~.index~~ = i;		cin >> queryL >> queryR;

			queries[i] = { queryL, queryR, queryL / blockSize, i });
	}		}

	2. Сортируем запросы сначала по возрастанию блока, затем по возрастанию правого конца:		2. Сортируем запросы сначала по возрастанию блока, затем по возрастанию правого конца:
	bool ~~compare~~(Query &~~a, Query &b~~) {		bool operator < (const Query &that) const {
	~~return tie~~(a.block~~, a.right~~) < ~~tie(b~~.block~~, b~~.~~right)~~;		if (block != that.block)
			return block < that.block;
			return r < that.r;
	}		}

	sort(queries, queries ~~+ queriesCount, compare~~);		sort(queries.begin(), queries.end());

	3. Заводим индексы l и r для начала и конца рабочего отрезка, рассчитываем ответ на рабочем отрезке:		3. Заводим индексы l и r для начала и конца рабочего отрезка, рассчитываем ответ на рабочем отрезке:
	int l = 0, r = 0~~, curAns =~~ .~~.. /* ответ для~~ [~~0..0~~] */;		Counter counter;
			int l = 0, r = 0;
			counter.add(a[l], 1);

	4. Обрабатываем запросы в порядке сортировки, втупую двигая l и r куда нужно и обновляя ответ для рабочего отрезка:		4. Обрабатываем запросы в порядке сортировки, втупую двигая l и r куда нужно и обновляя ответ для рабочего отрезка:
	for (~~int i = 0; i < queriesCount; i++~~) {		vector<int> res(queries.size());
	while (l ~~< queries[i].left~~) {		for (auto &[queryL, queryR, block, index] : queries) {
	.~~.. /* исключаем~~ a[l], ~~обновляем curAns */~~		while (queryL < l)
	~~l++~~;		counter.add(a[--l], 1);
	}		while (l < queryL)
	while (l ~~> queries[i].left~~) {		counter.add(a[l++], -1);
	~~l--;~~		while (queryR < r)
	.~~.. /* добавляем~~ a[l], ~~обновляем curAns */~~		counter.add(a[r--], -1);
	}		while (r < queryR)
	while (r ~~< queries[i].right~~) {		counter.add(a[++r], 1);
	~~r++;~~		res[index] = counter.getRes();
	.~~.. /* добавляем~~ a[r], ~~обновляем curAns */~~
	}
	while (r ~~> queries[i].right~~) {
	.~~.. /* исключаем~~ a[r], ~~обновляем curAns */~~
	~~r--~~;
	}
	~~ans[queries~~[~~i].~~index] = ~~curAns~~;
	}		}

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

	== ~~За сколько это работает~~ ==		== Сложность ==
	Предполагаем, что ~~curAns~~ обновляется за O(1).		Предполагаем, что ответ обновляется за O(1).

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

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

	== Ссылки ==		== Ссылки ==

Ctrlalt: /* Ссылки */

2021-06-29T20:20:09Z

Ссылки

← Предыдущая версия		Версия от 20:20, 29 июня 2021
Строка 72:		Строка 72:
	* [http://codeforces.com/blog/entry/72690 Codeforces — Mo's Algorithm (with and without update)]		* [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/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/86/problem/D Codeforces 86.D]

Ctrlalt: /* Ссылки */

2020-09-27T14:13:44Z

Ссылки

← Предыдущая версия		Версия от 14:13, 27 сентября 2020
Строка 71:		Строка 71:
	* [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)]		* [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]
	Задачи:		Задачи:
	* [http://codeforces.com/contest/86/problem/D Codeforces 86.D]		* [http://codeforces.com/contest/86/problem/D Codeforces 86.D]

Ctrlalt: /* Ссылки */

2020-01-09T12:39:29Z

Ссылки

← Предыдущая версия		Версия от 12:39, 9 января 2020
Строка 66:		Строка 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]

Ctrlalt: /* Ссылки */

2020-01-02T11:28:38Z

Ссылки

← Предыдущая версия		Версия от 11:28, 2 января 2020
Строка 69:		Строка 69:
	* [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]		* [http://codeforces.com/blog/entry/72690 Codeforces — Mo's Algorithm (with and without update)]
	Задачи:		Задачи:
	* [http://codeforces.com/contest/86/problem/D Codeforces 86.D]		* [http://codeforces.com/contest/86/problem/D Codeforces 86.D]

Ctrlalt: /* Ссылки */

2020-01-02T11:28:00Z

Ссылки

← Предыдущая версия		Версия от 11:28, 2 января 2020
Строка 69:		Строка 69:
	* [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]
	Задачи:		Задачи:
	* [http://codeforces.com/contest/86/problem/D Codeforces 86.D]		* [http://codeforces.com/contest/86/problem/D Codeforces 86.D]

Ctrlalt в 01:04, 3 августа 2019

2019-08-03T01:04:55Z

← Предыдущая версия		Версия от 01:04, 3 августа 2019
Строка 51:		Строка 51:
	ans[queries[i].index] = curAns;		ans[queries[i].index] = curAns;
	}		}
			Обрати внимание: в некоторых задачах важен порядок операций: например, сначала расширяем рабочий отрезок, затем сужаем.

	== За сколько это работает ==		== За сколько это работает ==
Строка 72:		Строка 73:
	* [http://codeforces.com/contest/220/problem/B Codeforces 220.B]		* [http://codeforces.com/contest/220/problem/B Codeforces 220.B]
	* [http://www.spoj.com/problems/DQUERY SPOJ DQUERY]		* [http://www.spoj.com/problems/DQUERY SPOJ DQUERY]
	* [http://www.codechef.com/problems/IITI1 CodeChef IITI1] (понадобится сжатие координат и дерево Фенвика)		* [http://www.codechef.com/problems/IITI1 CodeChef IITI1] (понадобится дерамида или сжатие координат + дерево Фенвика)

Ctrlalt в 00:38, 3 августа 2019

2019-08-03T00:38:34Z

← Предыдущая версия		Версия от 00:38, 3 августа 2019
Строка 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/contest/220/problem/B Количество чисел x, встречающихся x раз на отрезке]
			:* [http://www.codechef.com/problems/IITI15 Количество инверсий на отрезке]
	* Элементы массива не меняются;		* Элементы массива не меняются;
	* Ответ на запросы в оффлайне (запросы будут сортироваться, отвечать будем не в том порядке, в котором они даны).		* Ответ на запросы в оффлайне (запросы будут сортироваться, отвечать будем не в том порядке, в котором они даны).
Строка 72:		Строка 72:
	* [http://codeforces.com/contest/220/problem/B Codeforces 220.B]		* [http://codeforces.com/contest/220/problem/B Codeforces 220.B]
	* [http://www.spoj.com/problems/DQUERY SPOJ DQUERY]		* [http://www.spoj.com/problems/DQUERY SPOJ DQUERY]
			* [http://www.codechef.com/problems/IITI1 CodeChef IITI1] (понадобится сжатие координат и дерево Фенвика)

Ctrlalt в 22:30, 2 августа 2019

2019-08-02T22:30:10Z

← Предыдущая версия		Версия от 22:30, 2 августа 2019
Строка 4:		Строка 4:
	:* Наиболее частый элемент на отрезке		:* Наиболее частый элемент на отрезке
	:* Количество инверсий на отрезке		:* Количество инверсий на отрезке
	:* [http://codeforces.com/~~problemset~~/problem~~/220~~/B Количество чисел x, встречающихся x раз на отрезке]		:* [http://codeforces.com/contest/220/problem/B Количество чисел x, встречающихся x раз на отрезке]
	* Элементы массива не меняются;		* Элементы массива не меняются;
	* Ответ на запросы в оффлайне (запросы будут сортироваться, отвечать будем не в том порядке, в котором они даны).		* Ответ на запросы в оффлайне (запросы будут сортироваться, отвечать будем не в том порядке, в котором они даны).
Строка 68:		Строка 68:
	* [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/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]

Ctrlalt: /* Когда применяется */

2019-08-02T22:10:21Z

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

← Предыдущая версия		Версия от 22:10, 2 августа 2019
Строка 1:		Строка 1:
	== Когда применяется ==		== Когда применяется ==
	* Тяжёлые запросы на отрезках:		* Тяжёлые запросы на отрезках:
	:* Количество ~~инверсий~~ на отрезке;		:* [http://www.spoj.com/problems/DQUERY/ Количество различных элементов на отрезке]
	:* Наиболее частый элемент на отрезке;		:* Наиболее частый элемент на отрезке
	:* [http://codeforces.com/problemset/problem/220/B Количество чисел x, встречающихся x раз на отрезке;]		:* Количество инверсий на отрезке
			:* [http://codeforces.com/problemset/problem/220/B Количество чисел x, встречающихся x раз на отрезке]
	* Элементы массива не меняются;		* Элементы массива не меняются;
	* Ответ на запросы в оффлайне (запросы будут сортироваться, отвечать будем не в том порядке, в котором они даны).		* Ответ на запросы в оффлайне (запросы будут сортироваться, отвечать будем не в том порядке, в котором они даны).