Лекция по корневой декомпозиции
(14 марта 2018)
SQRT на массиве, plain
Задача 1
- += в точке
- сумма на отрезке
Задача 2.
- Дополнительно += на отрезке.
SQRT на массиве, блок cо СД внутри
- += на отрезке
- количество чисел ≤ x на отрезке.
Split-Rebuild SQRT
Задача:- sum на отрезке
- del(index)
- insert(index, value)
- split(pos): получить разрез в нужном месте
- rebuild(): получаем [0: n).
sum на отрезке выражаем через префиксные суммы виртуальной памяти.
complexity:
- split: O(#число отрезков)
- rebuild: O(#число отрезков + #длина массива)
- sum: split + O(#число отрезков).
- insert: split + O(1)
Вариации:
- Делаем split когда стало слишком много кусочков
- Поддерживаем инвариант, что каждый кусочек от sqrt(n) до 2 sqrt(n).
Сильно менее-приятная реализация, зато нет амортизации и можно хранить что-то внутри кусочка.
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
- add(x): добавить в сет новый элемент
- count(l..r): сколько элементов с такой суммой
Решение
Храним большом сортированном массиве и буферизируем новопришедшие числа отдельно.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))) на операцию.
Dynamic Connectivity Offline
Запросы:- connect(v, u)
- disconnect(v, u)
- connected?(v, u)
Решение
Бьём запросы на блоки по корню.Внутри блока не более корня рёбер меняют свой статус присутствия.
Сжимаем все стабильные компоненты связности, а дальше работаем в тупую за dfs.
В графе не более n вершин и 2k рёбер, обращаем внимание, что dfs работает за O(k), а не за O(n).
k := sqrt(n) => время работы O(n sqrt(n)).
Чтобы сделать dfs за O(k) можно использовать "быстрое очищение" массива used. Это можно сделать одним из двух способов:
- Запоминать те вершины, что мы пометили как used в стек, а потом его откатить.
- Использовать метки текущего времени. Вершина помечена, если used[v] == cur_t, операция cur_t++ очищает used.
SQRT-на-графе
Задача на графе.
Запросы:- color[vertex] := c
- найти количество различных цветов у соседей вершины v
Решение
Если бы все степени были маленькие, скажем меньше корня, то у нас есть очевидное решение: каждый раз перебираем всех соседей.Значит нужно как-то научится решать задачу для жирных вершин. sum_v deg(v) = 2E => жирных не более O(sqrt(E)).
Заранее насчитаем "базовый ответ" (с массивом/set) для всех жирных вершин.
Каждый раз когда перекрашиваем вершину пробегаем по всем её
SQRT со строками
Задача про строки
Дан текст и некоторый набор строк-шаблоновНайти (например посчитать суммарное количество) всех совпадений. Текст ограничен как 1e5, суммарная длина шаблонов такая же.
Решение:
Суммарная длина шаблонов 1e5 => количествоЕсли бы все шаблоны были бы одной длины, то мы можем решать задачу хешами.
Если разных, то сгруппируем по длине и переберём длину.
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).
Дмитрий Саютин, сборы в ДТЮ