17
правок
Изменения
Нет описания правки
Допустим, что текущий рабочий отрезок — <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>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>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>3 \cdot N + Q_i \cdot K</tex> операций <tex>\mathtt{add}</tex> и <tex>\mathtt{del}</tex> где <tex>Q_i</tex> {{---}} количество запросов, принадлежащих группе под номером <tex>i</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{addRight}</tex> произойдёт суммарно не больше чем <tex>N</tex> раз, так как минимальная правая граница {{---}} <tex>1</tex>, а максимальная {{---}} <tex>N</tex>
'''int''' K = sqrt(N)
'''int''' a = 1, b = 0 <font color=green>// создаём пустой рабочий отрезок</font>
'''bool''' isLess('''Query''' a, '''Query''' b):
'''if''' (a.l / K != b.l / K):
'''return''' a.l < b.l
'''return''' a.r < b.r
'''function''' process('''Query'''[Q] q):
sort(q, isLess) <font color=green>// сортируем запросы, используя функцию '''isLess''' как оператор сравнения</font>
'''intfor''' a = 1, b i = 0 <font color=green>// создаём пустой рабочий отрезок</font> '''forto''' i = 0 to Q - 1:
'''while''' a > q[i].l:
addLeft(a - 1)
delRight(b)
b -= 1
result[q[i].id] = answer()<font color=green>// получаем ответ на [a;b] </font>
Рассмотрим для наглядности решение задачи нахождения моды на отрезке:
==Источники информации==
* [https://www.hackerearth.com/practice/notes/mos-algorithm/ HackerEarth - Mo's algorithm]
[[Категория:Сортировки]]
[[Категория:Дискретная_математика,_алгоритмы_и_структуры_данных#.D0.97.D0.B0.D0.B4.D0.B0.D1.87.D0.B0_.D0.BE_.D0.BD.D0.B0.D0.B8.D0.BC.D0.B5.D0.BD.D1.8C.D1.88.D0.B5.D0.BC_.D0.BE.D0.B1.D1.89.D0.B5.D0.BC_.D0.BF.D1.80.D0.B5.D0.B4.D0.BA.D0.B5]]
