Структуры данных (16 октября 2014)

1. Разбор: 4С.function, тараканы
2. Bucket sort. Сортировка за линейное время.
3. СНМ на основе списков: get за O(1), join-ы в сумме O(nlogn)
4. Дерево отрезков снизу сверху
1. Сверху: += на отрезке, = на отрезке, проталкивание вниз
5. Решение задач
1. feelgood: даны a_i > 0, найти отрезок такой, что min × ∑ → max
1. Напоминание: решение за O(n)
2. Решение с помощью СНМ
3. Решение деревом отрезков
2. painter: число черных отрезков, суммарная длина черного, операция "покрасить отрезок"
3. Другие операции на отрезке: произведение чисел на отрезке, произведение матриц, сумма линейных функций, gcd на отрезке
4. Заметающая, она же сканирующая, прямая
1. Выбрать самую тяжелую (сумма весов) последовательность точек на плоскости, упорядоченных и по x, и по y. Сжатие координат.
2. Для каждого из m прямоугольников найти количество точек в нем. O((n+m)logn)