Лекция по корневой декомпозиции

(14 марта 2018)

SQRT на массиве, plain

Задача 1

Разбиваем массив на корень кусочков. В каждом кусочке храним соответствующий массив-подотрезок и его сумму.

Задача 2.

Дополнительно храним модификатор в каждом блоке. Проталкиваем когда нужно.

SQRT на массиве, блок cо СД внутри

Решение: поддерживаем для каждого отрезка обычный и сортированный массив.

Split-Rebuild SQRT

Задача: Массив "виртуальной памяти". Список "отрезков-указателей". Остальные операции выражаем через split.

sum на отрезке выражаем через префиксные суммы виртуальной памяти.

complexity: Невыгодно иметь много отрезков. Каждые sqrt(n) операций делаем Rebuild => мы в шоколаде.

Вариации:

sqrt-декомпозиция по запросам

Задача: Винни-Пух и бочки мёда

Много бочек мёда. В i-ой изначально ai мёда и объём bi.
Затем операции на отрезке c l по r первой "+= a", второй += "a + b", третий += "a + 2b", и т.д.
Вывести для каждой бочки первый запрос, когда она заполнится.
Решение
Разгребаем запросы блоками по k=корню

Если предположить, что никакой бочонок не переполняется, то не очень сложно c помощью сканлайна за O(k + n) найти итоговый объём каждого бочонка.

Если бочонок не наполнился, то всё ок.

Иначе наполнился, при чём после выполнения алгоритма выше мы такие бочонки все и найдём.

Для каждого такого ещё раз просимулируем k запросов за O(k). И найдём его ответ.
Итого O((k + n) n/k) + O(nk) => k = sqrt(n) и O(n sqrt(n)).

Задача про set

Решение
Храним большом сортированном массиве и буферизируем новопришедшие числа отдельно.

count делает бинарный поиск в большом массиве и пробегается по всему малому, O(log(n) + sqrt(n)).

add либо просто добавляет в малый массиве, либо сливает два массива на O(n log (n)).

Среди фазы размером k + 1 add получается k раз время O(1) и один раз O(n log(n)).

При выборе k = sqrt(n log(n)) получаем решение за O(sqrt(n log(n))) на операцию.

Можно перестраивать большой массив за O(n), если отсортировать малый отдельно и сделать merge

Dynamic Connectivity Offline

Запросы: Все запросы даны в offline.

Решение

Бьём запросы на блоки по корню.

Внутри блока не более корня рёбер меняют свой статус присутствия.

Сжимаем все стабильные компоненты связности, а дальше работаем в тупую за dfs.

В графе не более n вершин и 2k рёбер, обращаем внимание, что dfs работает за O(k), а не за O(n).

k := sqrt(n) => время работы O(n sqrt(n)).

Чтобы сделать dfs за O(k) можно использовать "быстрое очищение" массива used. Это можно сделать одним из двух способов:

SQRT-на-графе

Задача на графе.

Запросы:

Решение

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

Значит нужно как-то научится решать задачу для жирных вершин. sum_v deg(v) = 2E => жирных не более O(sqrt(E)).

Заранее насчитаем "базовый ответ" (с массивом/set) для всех жирных вершин.
Каждый раз когда перекрашиваем вершину пробегаем по всем её жирным соседям Их не более корня, так как глобально тоже не более корня (но нужно отдельно сохранить жирный подсписок).

SQRT со строками

Задача про строки

Дан текст и некоторый набор строк-шаблонов

Найти (например посчитать суммарное количество) всех совпадений. Текст ограничен как 1e5, суммарная длина шаблонов такая же.

Решение:

Суммарная длина шаблонов 1e5 => количество различных длин не более sqrt(2e5).

Если бы все шаблоны были бы одной длины, то мы можем решать задачу хешами.
Если разных, то сгруппируем по длине и переберём длину.

MO

Задача min на отрезке

Решение:

Если знать (multi)-set значений, которые есть на отрезке, то ответ легко вычилисть

Если насчитать set для одного отрезка, то можно его легко сдвигать, за O(log n) на одну позицию.

Если правильно определить отсортировать все отрезки, то получается O(n sqrt(n) log(n)).

Отрезки выгодно сортировать по <l/k, r>

MO-fast

Быстрее: Тоже самое, только используем как внутреннюю структуру данных корневую.

Замечаем, что МО работает за O(n sqrt(n) * время-сдвига + n * время-запроса).

Выгодно перебалансировать в сторону второго.

O(n sqrt(n)).

MO + обновления

Мир в 3D. Общая концепция.

Сортировать выгодно по <t/k, l/k, r>

O(n5/3).

Дмитрий Саютин, сборы в ДТЮ