Алгоритм Мо: отвечать на запросы не в том порядке, в каком спросили

Если ты знаешь, как упорядочить запросы по Мо, почему это даёт (n+q)·√n сдвигов и когда метод неприменим, листай до «Теперь сам».

Как думаешь, что делать с вопросом, который не складывается

Дерево отрезков отвечало на «сумму на отрезке», потому что сумма отрезка - это сумма сумм его половинок. А сколько различных чисел на отрезке? Знание «в левой половине 5 различных, в правой 7» ничего не говорит о целом: общих значений может быть сколько угодно.

Зато ответ легко ПОДПРАВИТЬ: если держать счётчики значений на текущем отрезке, добавление или удаление одного элемента с краю меняет число различных за O(1). Прежде чем читать дальше, ответь себе: 20 тысяч запросов к массиву из 20 тысяч элементов, указатели идут от запроса к запросу в том порядке, как запросы пришли. Сколько примерно шагов они сделают?

На что это похоже

Курьер с пачкой заказов по одной длинной улице. Развозить в порядке поступления - значит метаться от одного конца улицы к другому. Разумный курьер сортирует заказы: делит улицу на кварталы и внутри квартала едет в одну сторону. Заказы те же, ответы клиентам те же, а пробег в десятки раз меньше. Алгоритм Мо - это курьер, у которого два «края» отрезка, и оба надо подвезти к каждому запросу.

Механизм: блоки по √n и два указателя

текущий отрезок [L, R), счётчики значений на нём, ответ для него

добавить(i):  счётчик[a[i]] += 1;  если стал 1 - различных +1
убрать(i):    счётчик[a[i]] −= 1;  если стал 0 - различных −1

для запроса [l, r): двигать R к r и L к l по одному элементу,
                    вызывая добавить / убрать, - и записать ответ

ПОРЯДОК ЗАПРОСОВ:  блок = ⌊l / √n⌋, затем по r
                   (в нечётных блоках - по убыванию r: «змейка»)

Почему это дёшево. Запросы с левым концом в одном блоке идут подряд и по возрастанию r: правый указатель внутри блока движется только вперёд, не больше n шагов. Переход к началу обработки следующего блока тоже стоит не больше n. Блоков O(√n), поэтому правый указатель суммарно делает O(n·√n) шагов. Левый конец внутри одного блока прыгает не больше чем на √n за запрос: суммарно O(q·√n). Между непустыми блоками он может прыгнуть гораздо дальше, если промежуточные блоки пропущены. Но номера блоков растут: продвижение через их диапазоны и отклонения в пределах блоков суммарно стоят O(n). Итого для левого O(q·√n + n), для обоих O((n + q)·√n) сдвигов.

Змейка - мелкое улучшение: в нечётных блоках r идёт по убыванию, и правому указателю не нужно возвращаться к малым r при каждой смене блока. Это часто уменьшает число шагов правого указателя; точный выигрыш зависит от запросов.

Правило

Если все запросы к отрезкам известны заранее, а ответ легко подправить при добавлении и удалении элемента с края, запросы переставляют: сортируют по блоку ⌊l/√n⌋, а внутри блока - по r (змейкой). Два указателя ходят от запроса к запросу с пересчётом за O(1) на шаг; всего O((n + q)·√n) шагов вместо O(n·q) в порядке поступления. Ответы записывают по номеру запроса и выдают в исходном порядке. Метод работает только ОФЛАЙН и только для «добавляемых и удаляемых» ответов.

Разбор: пять запросов на девяти элементах

n = 9, блок длины 3. Запросы [l, r):  (0,5) (6,9) (1,3) (4,8) (2,9)
указатели стартуют с L = R = 0

как пришли:   (0,5): 5   (6,9): 6+4   (1,3): 5+6   (4,8): 3+5
              (2,9): 2+1                         всего 37 шагов

по Мо:  блок 0 (l = 0..2), r по возрастанию:  (1,3) (0,5) (2,9)
        блок 1 (l = 3..5), r по убыванию:     (4,8)
        блок 2 (l = 6..8), r по возрастанию:  (6,9)
        (1,3): 1+3   (0,5): 1+2   (2,9): 2+4   (4,8): 2+1   (6,9): 2+1
                                                 всего 19 шагов

Уже на пяти запросах вдвое меньше; при тысячах запросов разница становится порядками.

Разбор: двадцать тысяч запросов о различных значениях

Программа считает шаги указателей в порядке поступления и в порядке Мо, затем отвечает на все запросы по Мо - сколько различных значений на отрезке - и сверяет 200 ответов с перебором.

import math
import random

rng = random.Random(4)
n = q = 20000
a = [rng.randrange(5000) for _ in range(n)]
zaprosy = []
for _ in range(q):
    l = rng.randrange(n)
    zaprosy.append((l, rng.randrange(l, n) + 1))   # отрезок [l, r)


def peremeshcheniya(poryadok):        # сколько шагов сделают указатели
    L = R = 0
    s = 0
    for l, r in poryadok:
        s += abs(l - L) + abs(r - R)
        L, R = l, r
    return s


blok = int(math.sqrt(n))


def klyuch_mo(z):                     # блок левого конца, затем правый
    l, r = z
    return (l // blok, r if (l // blok) % 2 == 0 else -r)


po_mo = sorted(zaprosy, key=klyuch_mo)
print("шагов указателей как пришли:", peremeshcheniya(zaprosy))
print("шагов указателей по Мо:     ", peremeshcheniya(po_mo))

skolko = [0] * 5000                   # различных на отрезке - по Мо
raznyh, L, R, otvet = 0, 0, 0, {}
for l, r in po_mo:
    while R < r:
        skolko[a[R]] += 1
        raznyh += skolko[a[R]] == 1
        R += 1
    while L > l:
        L -= 1
        skolko[a[L]] += 1
        raznyh += skolko[a[L]] == 1
    while R > r:
        R -= 1
        skolko[a[R]] -= 1
        raznyh -= skolko[a[R]] == 0
    while L < l:
        skolko[a[L]] -= 1
        raznyh -= skolko[a[L]] == 0
        L += 1
    otvet[(l, r)] = raznyh
for l, r in zaprosy[:200]:            # выборочная сверка с перебором
    assert otvet[(l, r)] == len(set(a[l:r]))
print("сверено с перебором: 200 запросов")

шагов указателей как пришли: 230400537
шагов указателей по Мо:      2359125
сверено с перебором: 200 запросов

Двести тридцать миллионов шагов против двух с третью миллионов - почти в сто раз меньше. Оценка (n + q)·√n ≈ 40000 · 141 ≈ 5.6 миллиона задаёт масштаб асимптотической оценки, а не точный верхний предел с константой 1. В этом наборе змейка и случайные концы дают меньше шагов. Порядок поступления дал около 0.58·n шагов на запрос: соседние случайные отрезки отстоят друг от друга в среднем на треть массива по левому концу и чуть меньше - по правому.

Что ломается без этого

Первая ошибка - применить Мо к запросам, которые приходят по одному и требуют ответа сразу (онлайн): переставлять нечего, и метод не работает. Вторая - взять ответ, который нельзя подправить при УДАЛЕНИИ: максимум на отрезке легко пересчитать при добавлении, но при удалении максимального элемента следующий максимум неизвестен - нужна куча или другой вариант метода. Третья - выдать ответы в порядке Мо: запросы переставлены, и ответ надо сохранить по номеру исходного запроса. Размер блока тоже влияет на цену: для длины B указатели делают O(qB + n²/B + n) шагов. B около √n - стандартный выбор, особенно когда q порядка n. Блок 1 может заставить правый указатель повторять длинные проходы, блок n - левый. Если q сильно отличается от n, полезно подобрать B по этой оценке.

Зачем это в работе

Офлайн-обработка - нормальный режим аналитики: отчёт «сколько уникальных пользователей было в каждом из этих десяти тысяч временных окон» считают пачкой, и порядок окон выбирает программа, а не заказчик. Та же идея «переставь запросы, чтобы соседние были похожи» стоит за сортировкой запросов к диску по номеру блока, за группировкой операций в базе по ключу и за упорядочиванием тайлов при отрисовке карты. Сама сортировка по блоку √n - частный случай приёма «разбей на корень из n кусков», который ещё не раз выручит там, где логарифмическая структура не строится.

Теперь сам

n = 100, блок 10. Запросы [l, r): (35,90), (12,40), (31,60), (5,70), (18,25), (39,95). Расставь их в порядке Мо со змейкой.