Корневые оптимизации
Корневая декомпозиция
Рассмотрим такую задачу
Мы хотим делать две операции:
1) a[l; r] += x
2) a[l; r] < x
Решение:
Разобьем наш массив на K блоков (спойлер. K = √n)
Тогда наш отрезок запроса разобьется на неполные блоки (по краям), а так же на полные блоки
Для каждого неполного блока сделаем операции в тупую за O(√n)
Для операции 1:
Будем хранить в массиве buff[i] (где i - номер блока) - сколько мы добавили в блок i
Будем хранить отсортированные отрезки. Отвечать будем на запросы с помощью Бинарного поиска за O(LogN) для блока. То есть возьмем числа, для которых верно: a[i] + buff[num(i)] < x
Алгоритм МО
Рассмотрим такую задачу
Дано много-много запросов, состоящий из границ отрезка и числа x
Вам нужно для каждого отрезка ответить на вопрос: Сколько чисел, лежащий в нашем отрезке равны x?
Решение:
Воспользуемся Алгоритмом МО
Для начала, чтобы все работало намного быстрее, чем сейчас - сожмем числа
То есть:
Пусть есть массив [1, 5, 3, 6, 1, 6] -> [1, 2, 3, 4, 1, 4]
Воспользуемся идеей из прошлой задачи и разобьем отрезки в блоки по левой границе. Внутри блока отсортируем их по правой границе
Дальше, внутри каждого нового блока посчитаем ответ в тупую для первого отрезка
Дальше, для каждого блока будем двигать левые границы в тупую, а правую - только направо
Тогда суммарно наша правая граница пройдет максимум N элементов => работает за O(N)
Военная хитрость:
Нечетные блоки отсортируем по возрастанию, четные - по убыванию (это будет работать быстрее)
Оптимизация какого-то что?
жесть там какие-то тяжелые и легкие вершины, но задача изи короче мне пофиг