Задачи (примеры) к теме перебор

1. Поезда: заказ = отрезок [L_i, R_i] и кол-во пассажиров K_i. Вместимость поезда = C, нужно Summ_i (R_i-L_i+1)*K_i → max
1. Полный перебор за 2^N
2. Отсечение по ответу
2. Самый длинный путь: разбор
1. Правильная меморизация. O(2^N) памяти.
2. Отсечение по ответу: dep + count > Best
3. Чтобы найти count каждый раз запускаем dfs

Задачи на Динамику

1. Число способов пройти по шахматной доске конем из (1,1) в (N,N) (ходить можно только вправо-вниз).
2. Маша и грибы (Маша ходит по матрице и собирает грибы, ходить можно только вниз и вправо, нельзя врезаться в деревья).

Задачи (примеры) на стурктуры данных

1. Найти подотрезок с максимальной суммой за O(N).
2. Найти подматрицу с максимальной суммой за O(N³).

Одномерные Структуры данных

1. Не меняющийся массив - продолжение
1. Минимум на отрезке фиксированной длины за O(1) с предподсчетом за O(N)
2. Обобщение до матрицы
2. Меняющийся массив - продолжение
1. Дерево Фенвика для суммы [logN]
2. 2D-Фенвик
3. LCA-RMQ продолжение
1. LCA в дереве = RMQ на отрезке (RMQ ±1) [Эйлеров обход за O(N)]
2. RMQ на отрезке = LCA в дереве [постоение Декартового Дерева за O(N)], получили LCA за [O(NlogN), O(1)]

Декартово дерево

1. (L, R) = Split(T, x)
2. T = Merge(L, R)
3. Add. Через Split-Merge и одним запросом сверху.
4. Del. Через Split-Merge и одним запросом сверху.
5. Find K-th.
6. Количество и сумма всех элементов со значениями из [L..R]
7. Построение за O(n)
8. Randomized Trees (y можно не хранить)

Декартово дерево по неявному ключу

1. Ключ = позиция элемента. Неявный, т.к. восстанавливается из size-ов.
2. Split и Merge для дерева по неявному ключу.
3. Вставка на i-ю позицию, удаление с i-й позиции
4. Поменять местами два подотрезка массива.
5. Reverse подотрезка массива.
6. Прибавление на отрезке, присваивание на отрезке.