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

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:06:03Z

rollbackEdits.php mass rollback

141.98.9.47 в 06:28, 1 сентября 2022

2022-09-01T06:28:44Z

188.127.40.52: Исправление "медианы" описанной как "число, которое встречается больше всех остальных" на "моду"

2021-12-22T10:50:04Z

Исправление "медианы" описанной как "число, которое встречается больше всех остальных" на "моду"

188.130.155.161 в 09:57, 11 июля 2021

2021-07-11T09:57:22Z

Noobgam в 16:08, 18 января 2017

2017-01-18T16:08:57Z

Noobgam в 23:11, 17 января 2017

2017-01-17T23:11:14Z

Noobgam: /* Алгоритм */

2017-01-17T23:05:42Z

‎Алгоритм

Noobgam в 21:19, 15 января 2017

2017-01-15T21:19:17Z

Noobgam в 21:17, 15 января 2017

2017-01-15T21:17:11Z

Noobgam в 21:10, 15 января 2017

2017-01-15T21:10:56Z

← Предыдущая		Версия 16:06, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	'''Алгоритм Мо''' (англ. ''Mo's algorithm'') — применяется для решения задач, в которых требуется отвечать на запросы <tex>arr[l \ldots r]</tex> на массиве		'''Алгоритм Мо''' (англ. ''Mo's algorithm'') — применяется для решения задач, в которых требуется отвечать на запросы <tex>arr[l \ldots r]</tex> на массиве
	''без'' изменения элементов в оффлайн за время <tex>O(Q \cdot \log{Q} + (N + Q) \cdot \sqrt{N})</tex>, где <tex>Q</tex> {{---}} количество запросов,		''без'' изменения элементов в оффлайн за время <tex>O(Q \cdot \log{Q} + (N + Q) \cdot \sqrt{N})</tex>, где <tex>Q</tex> {{---}} количество запросов,

← Предыдущая		Версия 06:28, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	'''Алгоритм Мо''' (англ. ''Mo's algorithm'') — применяется для решения задач, в которых требуется отвечать на запросы <tex>arr[l \ldots r]</tex> на массиве		'''Алгоритм Мо''' (англ. ''Mo's algorithm'') — применяется для решения задач, в которых требуется отвечать на запросы <tex>arr[l \ldots r]</tex> на массиве
	''без'' изменения элементов в оффлайн за время <tex>O(Q \cdot \log{Q} + (N + Q) \cdot \sqrt{N})</tex>, где <tex>Q</tex> {{---}} количество запросов,		''без'' изменения элементов в оффлайн за время <tex>O(Q \cdot \log{Q} + (N + Q) \cdot \sqrt{N})</tex>, где <tex>Q</tex> {{---}} количество запросов,

@@ Строка 1: / Строка 1: @@
 '''Алгоритм Мо''' (англ. ''Mo's algorithm'') — применяется для решения задач, в которых требуется отвечать на запросы <tex>arr[l \ldots r]</tex> на массиве
 ''без'' изменения элементов в оффлайн за время <tex>O(Q \cdot \log{Q} + (N + Q) \cdot \sqrt{N})</tex>, где <tex>Q</tex> {{---}} количество запросов,
-а <tex>N</tex> {{---}} количество элементов в массиве. Характерными примерами задач на этот алгоритм являются: нахождение медианы на отрезке (число, которое встречается больше всех остальных),
+а <tex>N</tex> {{---}} количество элементов в массиве. Характерными примерами задач на этот алгоритм являются: нахождение моды на отрезке (число, которое встречается больше всех остальных),
 вычисление количества инверсий на отрезке.

@@ Строка 1: / Строка 1: @@
 '''Алгоритм Мо''' (англ. ''Mo's algorithm'') — применяется для решения задач, в которых требуется отвечать на запросы <tex>arr[l \ldots r]</tex> на массиве
 ''без'' изменения элементов в оффлайн за время <tex>O(Q \cdot \log{Q} + (N + Q) \cdot \sqrt{N})</tex>, где <tex>Q</tex> {{---}} количество запросов,
-а <tex>N</tex> {{---}} количество элементов в массиве. Характерными примерами задач на этот алгоритм являются: нахождение моды на отрезке (число, которое встречается больше всех остальных),
+а <tex>N</tex> {{---}} количество элементов в массиве. Характерными примерами задач на этот алгоритм являются: нахождение медианы на отрезке (число, которое встречается больше всех остальных),
 вычисление количества инверсий на отрезке.

@@ Строка 7: / Строка 7: @@
 В каждый момент времени будем хранить непрерывный отрезок <tex>[a \ldots b]</tex> исходного массива (будем называть его рабочим отрезком), вместе со структурой данных,
 которая умеет обрабатывать следующие операции:
-* <tex>\mathtt{addLeft(a-1)}</tex>, <tex>\mathtt{addRight(b+1)}</tex> {{---}} операции, которые позволяют добавить элемент в рабочий отрезок слева и справа соответственно.
+* <tex>\mathtt{addLeft(a-1)}</tex>, <tex>\mathtt{addRight(b+1)}</tex> {{---}} операции, которые позволяют добавить элемент в рабочий отрезок слева и справа соответственно;
-* <tex>\mathtt{delLeft(a)}</tex>, <tex>\mathtt{delRight(b)}</tex> {{---}} операции, которые позволяют удалить элемент рабочего отрезка слева и справа соответственно.
+* <tex>\mathtt{delLeft(a)}</tex>, <tex>\mathtt{delRight(b)}</tex> {{---}} операции, которые позволяют удалить элемент рабочего отрезка слева и справа соответственно;
-* <tex>\mathtt{answer}</tex> {{---}} операция, которая позволяет получить ответ на запрос, если бы его границами был рабочий отрезок;
+* <tex>\mathtt{answer}</tex> {{---}} операция, которая позволяет получить ответ на запрос, если бы его границами был рабочий отрезок.
 Изначально в качестве рабочего отрезка можно взять любой отрезок. Для удобства чтения будем считать изначальным отрезок <tex>[1;1)</tex>, то есть <tex>a = 1</tex>, <tex>b = 0</tex>, фактически {{---}} пустой отрезок.
-Запишем все запросы в массив, некоторым образом их отсортируем (как конкретно - будет сказано чуть позже) будем их обрабатывать в том порядке, в котором они будут лежать в массиве после [[Сортировки | сортировки]].
+Запишем все запросы в массив, отсортируем их определённым способом (который будет описан ниже) будем их обрабатывать в том порядке, в котором они будут лежать в массиве после [[Сортировки | сортировки]].
-Допустим, что текущий рабочий отрезок — <tex>[a \ldots b]</tex>, а первый необработанный запрос — <tex>[l_i, r_i]</tex> тогда сначала расширим наш отрезок,
+Допустим, что текущий рабочий отрезок — <tex>[a \ldots b]</tex>, а первый необработанный запрос — <tex>[l_i, r_i]</tex> тогда рассмотрим случаи:
-используя только операции <tex>\mathtt{addLeft}</tex>, <tex>\mathtt{addRight}</tex> до отрезка <tex>[l \ldots r]</tex>,
+* Если изначально было <tex> a > l_i </tex>, то будем добавлять в рабочий отрезок элементы слева по одному, пока граница не совпадёт;
-где <tex>l = \min(a, l_i)</tex>, а <tex>r = \max(b, r_i)</tex>, а затем удалим лишние элементы при помощи операций <tex>\mathtt{delLeft}</tex>, <tex>\mathtt{delRight}</tex>, чтобы получить отрезок <tex>[l_i \ldots r_i]</tex>, после чего вызовем <tex>\mathtt{answer}</tex> и запомним ответ для этого запроса.
+* Если же это не так, то есть <tex> a < l_i </tex> это значит, что в рабочем отрезке присутствуют те элементы, которых там быть не должно, и они должны быть удалены;
 Теперь разберём поподробнее, как именно следует сортировать запросы для достижения вышеназванной асимптотики по времени.
@@ Строка 28: / Строка 31: @@
 Для этого рассмотрим отдельно количество сделанных операций каждого из четырёх типов:
-* изначально, до обработки группы, рабочий отрезок был <tex>[a \ldots b]</tex>, для обработки первого запроса может потребоваться <tex>2 \cdot N</tex> операций <tex>\mathtt{add}</tex>, <tex>\mathtt{del}</tex>
+* изначально, до обработки группы, рабочий отрезок был <tex>[a \ldots b]</tex>, для обработки первого запроса может потребоваться <tex>2 \cdot N</tex> операций <tex>\mathtt{add}</tex>, <tex>\mathtt{del}</tex>;
-* <tex>\mathtt{delRight}</tex> между отрезками одной группы не произойдёт ни разу, так как рабочий отрезок внутри одной группы будет только расширяться в сторону правого конца
+* <tex>\mathtt{delRight}</tex> между отрезками одной группы не произойдёт ни разу, так как рабочий отрезок внутри одной группы будет только расширяться в сторону правого конца;
-* <tex>\mathtt{addRight}</tex> в этой группе произойдёт суммарно не больше чем <tex>N</tex> раз, так как минимальная правая граница {{---}} <tex>1</tex>, а максимальная {{---}} <tex>N</tex>
+* <tex>\mathtt{addRight}</tex> в этой группе произойдёт суммарно не больше чем <tex>N</tex> раз, так как минимальная правая граница {{---}} <tex>1</tex>, а максимальная {{---}} <tex>N</tex>;
-* для оставшихся двух операций рассмотрим два последовательных запроса <tex>[l_i \ldots r_i]</tex>, <tex>[l_j \ldots r_j]</tex>. Нетрудно заметить, что так как отрезки принадлежат одной группе, то <tex>|l_i - l_j| < K</tex>, следовательно, количество операций <tex>\mathtt{addLeft}</tex> или <tex>\mathtt{delLeft}</tex> не будет превосходить <tex>K</tex>, а суммарно для всей группы {{---}} <tex>Q_i \cdot K</tex>;
+* для оставшихся двух операций рассмотрим два последовательных запроса <tex>[l_i \ldots r_i]</tex>, <tex>[l_j \ldots r_j]</tex>. Нетрудно заметить, что так как отрезки принадлежат одной группе, то <tex>|l_i - l_j| < K</tex>, следовательно, количество операций <tex>\mathtt{addLeft}</tex> или <tex>\mathtt{delLeft}</tex> не будет превосходить <tex>K</tex>, а суммарно для всей группы {{---}} <tex>Q_i \cdot K</tex>.
 Таким образом, нетрудно видеть, все группы будут обработаны за время <tex>O \left( \dfrac{N^2}{K}  + K \cdot Q \right) </tex>.
-При выборе <tex>K = \sqrt{N}</tex> с учётом сортировки по правой границе получается асимптотика времени <tex>O(Q \cdot \log Q + (N + Q) \cdot \sqrt N)</tex>
+При выборе <tex>K = \sqrt{N}</tex> с учётом сортировки по правой границе получается асимптотика времени <tex>O(Q \cdot \log Q + (N + Q) \cdot \sqrt N)</tex>.
 ==Реализация==
@@ Строка 89: / Строка 92: @@
     '''return''' current.max.second <font color=green>// находим максимальную пару в множестве</font>
-Итоговая асимптотика решения: <tex>O(Q \cdot \log Q + (N + Q) \cdot \sqrt{N} \cdot \log N)</tex>
+Итоговая асимптотика решения: <tex>O(Q \cdot \log Q + (N + Q) \cdot \sqrt{N} \cdot \log N)</tex>.
 == См. также ==

@@ Строка 13: / Строка 13: @@
 Изначально в качестве рабочего отрезка можно взять любой отрезок. Для удобства чтения будем считать изначальным отрезок <tex>[1;1)</tex>, то есть <tex>a = 1</tex>, <tex>b = 0</tex>, фактически {{---}} пустой отрезок.
-Запишем все запросы в массив, некоторым образом их отсортируем и будем их обрабатывать в том порядке, в котором они будут лежать в массиве после [[Сортировки | сортировки]].
+Запишем все запросы в массив, некоторым образом их отсортируем (как конкретно требуется сортировать будет сказано чуть позже) будем их обрабатывать в том порядке, в котором они будут лежать в массиве после [[Сортировки | сортировки]].
 Допустим, что текущий рабочий отрезок — <tex>[a \ldots b]</tex>, а первый необработанный запрос — <tex>[l_i, r_i]</tex> тогда сначала расширим наш отрезок,
@@ Строка 22: / Строка 22: @@
 Разделим все запросы на блоки размера <tex>K</tex> по левой границе: те запросы, для которых <tex>1 \leqslant l_i \leqslant K</tex> {{---}} попадают в первую группу,
 те запросы, для которых <tex>K + 1 \leqslant l_i \leqslant 2 \cdot K</tex> {{---}} во вторую, <tex>2 \cdot K + 1 \leqslant l_i \leqslant 3 \cdot K</tex> {{---}} в третью, и так далее. Будем рассматривать все группы запросов независимо друг от друга. Если внутри каждой группы отсортировать запросы увеличению правой границы, то асимптотика по времени для обработки одной группы будет <tex>O(N + Q_i \cdot K)</tex>, где <tex>Q_i</tex> {{---}} количество запросов, принадлежащих группе под номером <tex>i</tex>.
 ==Доказательство==